c,algorithm,math,recursion , Power by squaring for negative exponents

## Question:

Tag: c,algorithm,math,recursion

I am not sure if power by squaring takes care of negative exponent. I implemented the following code which works for only positive numbers.

``````    #include <stdio.h>
int powe(int x, int exp)
{
if (x == 0)
return 1;
if (x == 1)
return x;
if (x&1)
return powe(x*x, exp/2);
else
return x*powe(x*x, (exp-1)/2);
}
``````

Looking at https://en.wikipedia.org/wiki/Exponentiation_by_squaring doesn't help as the following code seems wrong.

``````    Function exp-by-squaring(x, n )
if n < 0  then return exp-by-squaring(1 / x, - n );
else if n = 0  then return  1;
else if n = 1  then return  x ;
else if n is even  then return exp-by-squaring(x * x,  n / 2);
else if n is odd  then return x * exp-by-squaring(x * x, (n - 1) / 2).
``````

Edit: Thanks to amit this solution works for both negative and positive numbers:

``````    float powe(float x, int exp)
{
if (exp < 0)
return powe(1/x, -exp);
if (exp == 0)
return 1;
if (exp == 1)
return x;
if (((int)exp)%2==0)
return powe(x*x, exp/2);
else
return x*powe(x*x, (exp-1)/2);
}
``````

For fractional exponent need to think though.

Answer:

Integer examples are for 32 bit `int` arithmetics, `DWORD` is 32bit `unsigned int`

1. floating `pow(x,y)=x^y`

2. integer `pow(a,b)=a^b` where `a>=0 , b>=0`

• this is easy (you already have that) done by squaring

``````DWORD powuu(DWORD a,DWORD b)
{
int i,bits=32;
DWORD d=1;
for (i=0;i<bits;i++)
{
d*=d;
if (DWORD(b&0x80000000)) d*=a;
b<<=1;
}
return d;
}
``````
3. integer `pow(a,b)=a^b` where `b>=0`

• just add few ifs to handle the negative a

``````int powiu(int a,DWORD b)
{
int sig=0,c;
if ((a<0)&&(DWORD(b&1)) { sig=1; a=-a; } // negative output only if a<0 and b is odd
c=powuu(a,b); if (sig) c=-c;
return c;
}
``````
4. integer `pow(a,b)=a^b`

• so if `b<0` then it means `1/powiu(a,-b)`
• as you can see the result is not integer at all
• so either ignore this case
• or return floating value
• or add a multiplier variable (so you can evaluate PI equations on pure Integer arithmetics)
• this is float result:

``````float powfii(int a,int b)
{
if (b<0) return 1.0/float(powiu(a,-b));
else return powiu(a,b);
}
``````
5. integer `pow(a,b)=a^b` where `b` is fractional

• you can do something like this `a^(1/bb)` where `bb` is integer
• in reality this is rooting
• so you can use binary search to evaluate
• `a^(1/2)` is `square root(a)`
• `a^(1/bb)` is `bb_root(a)`
• so do a binary search for c from MSB to LSB
• and evaluate if `pow(c,bb)<=a` then leave the bit as is else clear it
• this is sqrt example:

``````int bits(DWORD p) // count how many bits is p
{
DWORD m=0x80000000; int b=32;
for (;m;m>>=1,b--)
if (p>=m) break;
return b;
}

DWORD sqrt(const DWORD &x)
{
DWORD m,a;
m=(bits(x)>>1);
if (m) m=1<<m; else m=1;
for (a=0;m;m>>=1) { a|=m; if (a*a>x) a^=m; }
return a;
}
``````
• so now just change the `if (a*a>x)` with `if (pow(a,bb)>x)`

• where `bb=1/b` ... so b is fractional exponent you looking for and bb is integer
• also m is the number of bits of the result so change `m=(bits(x)>>1);` to `m=(bits(x)/bb);`

[edit1] fixed point sqrt example

``````//---------------------------------------------------------------------------
const int _fx32_fract=16;       // fractional bits count
const int _fx32_one  =1<<_fx32_fract;
DWORD fx32_mul(const DWORD &x,const DWORD &y)   // unsigned fixed point mul
{
DWORD a=x,b=y;              // asm has access only to local variables
asm {                       // compute (a*b)>>_fx32_fract
mov eax,a               // eax=a
mov ebx,b               // ebx=b
mul eax,ebx             // (edx,eax)=eax*ebx
mov ebx,_fx32_one
div ebx                 // eax=(edx,eax)>>_fx32_fract
mov a,eax;
}
return a;
}
DWORD fx32_sqrt(const DWORD &x) // unsigned fixed point sqrt
{
DWORD m,a;
if (!x) return 0;
m=bits(x);                  // integer bits
if (m>_fx32_fract) m-=_fx32_fract; else m=0;
m>>=1;                      // sqrt integer result is half of x integer bits
m=_fx32_one<<m;             // MSB of result mask
for (a=0;m;m>>=1)           // test bits from MSB to 0
{
a|=m;                   // bit set
if (fx32_mul(a,a)>x)    // if result is too big
a^=m;                  // bit clear
}
return a;
}
//---------------------------------------------------------------------------
``````
• so this is unsigned fixed point
• high 16 bits are integer
• low 16 bits are fractional part
• this is fp -> fx conversion: `DWORD(float(x)*float(_fx32_one))`
• this is fp <- fx conversion: `float(DWORD(x))/float(_fx32_one))`
• `fx32_mul(x,y)` is `x*y` it uses assembler of 80386+ 32bit architecture (you can rewrite it to karatsuba or whatever else to be platform independent)
• `fx32_sqrt(x)` is `sqrt(x)`
• in fixed point you should be avare of the fractional bit shift
• for multiplication: `(a<<16)*(b<<16)=(a*b<<32)`
• you need to shift back by `>>16` to get result `(a*b<<16)`
• also the result can overflow 32 bit therefore I use 64 bit result in assembly

[edit2] 32bit signed fixed point pow C++ example

When you put all the previous steps together you should have something like this:

``````//---------------------------------------------------------------------------
//--- 32bit signed fixed point format (2os complement)
//---------------------------------------------------------------------------
// |MSB              LSB|
// |integer|.|fractional|
//---------------------------------------------------------------------------
const int _fx32_bits=32;                                // all bits count
const int _fx32_fract_bits=16;                          // fractional bits count
const int _fx32_integ_bits=_fx32_bits-_fx32_fract_bits; // integer bits count
//---------------------------------------------------------------------------
const int _fx32_one       =1<<_fx32_fract_bits;         // constant=1.0 (fixed point)
const float _fx32_onef    =_fx32_one;                   // constant=1.0 (floating point)
const int _fx32_fract_mask=_fx32_one-1;                 // fractional bits mask
const int _fx32_integ_mask=0xFFFFFFFF-_fx32_fract_mask; // integer bits mask
const int _fx32_sMSB_mask =1<<(_fx32_bits-1);           // max signed bit mask
const int _fx32_uMSB_mask =1<<(_fx32_bits-2);           // max unsigned bit mask
//---------------------------------------------------------------------------
float fx32_get(int   x) { return float(x)/_fx32_onef; }
int   fx32_set(float x) { return int(float(x*_fx32_onef)); }
//---------------------------------------------------------------------------
int fx32_mul(const int &x,const int &y) // x*y
{
int a=x,b=y;                // asm has access only to local variables
asm {                       // compute (a*b)>>_fx32_fract
mov eax,a
mov ebx,b
mul eax,ebx             // (edx,eax)=a*b
mov ebx,_fx32_one
div ebx                 // eax=(a*b)>>_fx32_fract
mov a,eax;
}
return a;
}
//---------------------------------------------------------------------------
int fx32_div(const int &x,const int &y) // x/y
{
int a=x,b=y;                // asm has access only to local variables
asm {                       // compute (a*b)>>_fx32_fract
mov eax,a
mov ebx,_fx32_one
mul eax,ebx             // (edx,eax)=a<<_fx32_fract
mov ebx,b
div ebx                 // eax=(a<<_fx32_fract)/b
mov a,eax;
}
return a;
}
//---------------------------------------------------------------------------
int fx32_abs_sqrt(int x)            // |x|^(0.5)
{
int m,a;
if (!x) return 0;
if (x<0) x=-x;
m=bits(x);                  // integer bits
for (a=x,m=0;a;a>>=1,m++);  // count all bits
m-=_fx32_fract_bits;        // compute result integer bits (half of x integer bits)
if (m<0) m=0; m>>=1;
m=_fx32_one<<m;             // MSB of result mask
for (a=0;m;m>>=1)           // test bits from MSB to 0
{
a|=m;                   // bit set
if (fx32_mul(a,a)>x)    // if result is too big
a^=m;                  // bit clear
}
return a;
}
//---------------------------------------------------------------------------
int fx32_pow(int x,int y)       // x^y
{
// handle special cases
if (!y) return _fx32_one;                           // x^0 = 1
if (!x) return 0;                                   // 0^y = 0  if y!=0
if (y==-_fx32_one) return fx32_div(_fx32_one,x);    // x^-1 = 1/x
if (y==+_fx32_one) return x;                        // x^+1 = x
int m,a,b,_y; int sx,sy;
// handle the signs
sx=0; if (x<0) { sx=1; x=-x; }
sy=0; if (y<0) { sy=1; y=-y; }
_y=y&_fx32_fract_mask;      // _y fractional part of exponent
y=y&_fx32_integ_mask;      //  y integer part of exponent
a=_fx32_one;                // ini result
// powering by squaring x^y
if (y)
{
for (m=_fx32_uMSB_mask;(m>_fx32_one)&&(m>y);m>>=1);     // find mask of highest bit of exponent
for (;m>=_fx32_one;m>>=1)
{
a=fx32_mul(a,a);
if (int(y&m)) a=fx32_mul(a,x);
}
}
// powering by rooting x^_y
if (_y)
{
for (b=x,m=_fx32_one>>1;m;m>>=1)                            // use only fractional part
{
b=fx32_abs_sqrt(b);
if (int(_y&m)) a=fx32_mul(a,b);
}
}
// handle signs
if (sy) { if (a) a=fx32_div(_fx32_one,a); else a=0; /*Error*/ }     // underflow
if (sx) { if (_y) a=0; /*Error*/ else if(int(y&_fx32_one)) a=-a; }  // negative number ^ non integer exponent, here could add test if 1/_y is integer instead
return a;
}
//---------------------------------------------------------------------------
``````

I have tested it like this:

``````float a,b,c0,c1,d;
int x,y;
for (a=0.0,x=fx32_set(a);a<=10.0;a+=0.1,x=fx32_set(a))
for (b=-2.5,y=fx32_set(b);b<=2.5;b+=0.1,y=fx32_set(b))
{
if (!x) continue; // math pow has problems with this
if (!y) continue; // math pow has problems with this
c0=pow(a,b);
c1=fx32_get(fx32_pow(x,y));
d=0.0;
if (fabs(c1)<1e-3) d=c1-c0; else d=(c0/c1)-1.0;
if (fabs(d)>0.1)
d=d; // here add breakpoint to check inconsistencies with math pow
}
``````
• `a,b` are floating point
• `x,y` are closest fixed point representations of `a,b`
• `c0` is math pow result
• `c1` is fx32_pow result
• `d` is difference
• hope did not forget something trivial but it seems like it works properly
• do not forget that fixed point has very limited precision
• so the results will differ a bit ...

# Related:

## Program to reverse a string in C without declaring a char[]

c,string,pointers,char
I need to reverse a given string and display it without using the value At[index] notation , I tried the below program using pointers,but it does not print anything for the reverse string, Please help! int main() { char* name=malloc(256); printf("\nEnter string\n"); scanf("%s",name); printf("\nYou entered%s",name); int i,count; count=0; //find the...

## How does this code print odd and even?

c,if-statement,macros,logic
#define MACRO(num, str) {\ printf("%d", num);\ printf(" is");\ printf(" %s number", str);\ printf("\n");\ } int main(void) { int num; printf("Enter a number: "); scanf("%d", &num); if (num & 1) { MACRO(num, "Odd"); } else { MACRO(num, "Even"); } return 0; } Please explain the above code (if/else condition and how...

## Identify that a string could be a datetime object

python,regex,algorithm,python-2.7,datetime
If I knew the format in which a string represents date-time information, then I can easily use datetime.datetime.strptime(s, fmt). However, without knowing the format of the string beforehand, would it be possible to determine whether a given string contains something that could be parsed as a datetime object with the...

## Is post-increment operator guaranteed to run instantly?

c,c89,post-increment,ansi-c
Let's say I have the following code: int i = 0; func(i++, i++); The increment is happening right after returning the value? Is it guaranteed that the first argument will be 0, and the second argument will be 1?...

## Array breaking in Pebble C

c,arrays,pebble-watch,cloudpebble
I'm trying to create a simple dice-rolling application in Pebble using C on CloudPebble. I have an array of different die sizes you can scroll through using Up/Down, and you roll (currently just generate a random number, it'll get fancier later) using the middle button. There's also a label at...

## What is this algorithm mapping coordinates to numbers called?

algorithm,coordinates,coordinate-systems,coordinate
I'm writing a program for visualizing crystals. As a part of the program, I have to generate all different basic points in a lattice structure. For those that aren't familiar with crystallography, you can find the most general cases of these structures here: https://en.wikipedia.org/wiki/Hermann%E2%80%93Mauguin_notation#Lattice_types The problem was that I wanted...

## CallXXXMethod undefined using JNI in C

java,c,jni
So I've tried to use the JNI interface to call Java methods from C. Calling static methods is no problem, but I get stuck when I want to call a method on an object. The code is as follows: #include <stdio.h> #include <string.h> #include <jni.h> int main() { JavaVMOption options[1];...

## CGO converting Xlib XEvent struct to byte array?

c,go,xlib,cgo
I am creating a simple window manager (code based of the c code in tinywm) in Golang. To use Xlib, I am using cgo, so my header is: // #cgo LDFLAGS: -lX11 // #include <X11/Xlib.h> And I have a variable declaration, like: event := C.XEvent{} And then, I use this...

## Counting bytes received by posix read()

c,function,serial-port,posix
I get confused with one line of code: temp_uart_count = read(VCOM, temp_uart_data, 4096); I found more about read function at http://linux.die.net/man/3/read, but if everything is okay it returns 0, so how we can get num of bytes received from that? temp_uart_count is used to count how much bytes we received...

## Does realloc() invalidate all pointers?

c,pointers,dynamic-memory-allocation,behavior,realloc
Note, this question is not asking if realloc() invalidates pointers within the original block, but if it invalidates all the other pointers. I'm new to C, and am a bit confused about the nature of realloc(), specifically if it moves any other memory. For example: void* ptr1 = malloc(2); void*...

## Does there exist an algorithm for iterating through all strings that conform to a particular regex?

c#,regex,algorithm
I'm making a script to try and hack into an account whose login password is at least 8 characters long and includes at least 1 number, 1 special character and 1 capital letter. I will use brute force. Is there a compact, elegant and efficient way to iterate through every...

## Algorithm for [inclusive/exclusive]_scan in parallel proposal N3554

c++,algorithm,parallel-processing,c++14
Proposal N3554 (A Parallel Algorithms Library) for C++14, proposes (among other things), what seem to be parallel versions of the current std::partial_sum, e.g.: template< class ExecutionPolicy, class InputIterator, class OutputIterator, class BinaryOperation> OutputIterator inclusive_scan( ExecutionPolicy &&exec, InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); With the explanation Effects: For each...

## VS2012 Identifer not found when part of static lib

c,visual-studio-2012,linker,static-libraries
Using VS2012 C/C++: I created and linked a static lib called "libtools" to my project. Calls to functions in the libtools lib worked as expected. I created and linked a second static lib called "shunt" to my project. But when I incorporate a call to a function in shunt, I...

## Segmentation fault with generating an RSA and saving in ASN.1/DER?

c,openssl,cryptography,rsa
#include <string.h> #include <openssl/aes.h> #include <openssl/rand.h> #include <openssl/bio.h> #include <openssl/rsa.h> #include <openssl/evp.h> #include <openssl/pem.h> #define RSA_LEN 2048 #define RSA_FACTOR 65537 int genRSA2048(unsigned char **pub,unsigned int *pub_l,unsigned char **priv,unsigned int *priv_l){ RSA *pRSA = NULL; pRSA = RSA_generate_key(RSA_LEN,RSA_FACTOR,NULL,NULL); if (pRSA){ pub_l = malloc(sizeof(pub_l)); *pub_l = i2d_RSAPublicKey(pRSA,pub); priv_l = malloc(sizeof(priv_l));...

## What does `strcpy(x+1, SEQX)` do?

c,strcpy
I'm wondering what this syntax of strcpy() does in line 65 and 66: 24 #define SEQX "TTCATA" 25 #define SEQY "TGCTCGTA" 61 M = strlen(SEQX); 62 N = strlen(SEQY); 63 x = malloc(sizeof(char) * (M+2)); /* +2: leading blank, and trailing \0 */ 64 y = malloc(sizeof(char) * (N+2)); 65...

## Does strlen() always correctly report the number of char's in a pointer initialized string?

c,strlen
As long as I use the char and not some wchar_t type to declare a string will strlen() correctly report the number of chars in the string or are there some very specific cases I need to be aware of? Here is an example: char *something = "Report all my...

## How to increment the value of an unsigned char * (C)

c++,c,openssl,byte,sha1
I have a value stored as an unsigned char * (in C). This holds the SHA1 hash of a string. My goal is to cover the SHA1 key space. Since I'm using <openssl/evp.h> to generate the hashes, I end up with an unsigned char* holding the SHA1 value. Now I...

## Segmentation Fault if I don't say int i=0

c,arrays,segmentation-fault,initialization,int
void removeVowels(char* array){ int i,j,v; i=0; char vowel[]={'a','e','i','o','u'}; while(array[i]!='\0') { for(v=0;v<5;v++) { if (array[i]==vowel[v]) { j=i; while(array[j]!='\0') { array[j]=array[j+1]; j++; } i--; break; } } i++; } } in function removeVowels() if I don't include i=0; and just say int i; why does it give segmentation fault? Isn't it automatically...

## Text justification C language

c,text,alignment
I have to solve a problem that involves left justification string length and leading zeros. I have the following table : BEGIN CLOSE CONCATENATE DELETE END INITIALIZE PRINT WRITE This is produced by a simple program. My problem is to find out how to convert it like that : It...

## Is there Predefined-Macros define about byte order in armcc

c,armcc,predefined-macro
Is there Predefined-Macros define about byte order in armcc. I am a novice on the armcc.and sorry for my English. In gcc these are macros: __BYTE_ORDER__ __ORDER_LITTLE_ENDIAN__ __ORDER_BIG_ENDIAN__ __ORDER_PDP_ENDIAN__ ... Now I have to use armcc, Is there same like these with armcc? Thank a lot. by the way,the armcc...

## Disconnect all vertices in a graph - Algorithm

algorithm,graph
I am looking for an algorithm that finds minimal subset of vertices such that by removing this subset (and edges connecting these vertices) from graph all other vertices become unconnected (i.e. the graph won't have any edges). Is there such algorithm? If not: Could you recommend some kind of heuristics...

## Getting Wrong Answer in “Longest non regular parentheses sub-sequence ”codechef june cook off

algorithm
I attended a programming competition(it has ended now). I don't know why my solution is giving WA, I read the editorial, saw other people solution but unable to find a flaw in my solution. Obviously I am missing somewhere. Please help! Question Link My Solution My approach If the pattern...

## Reverse ^ operator for decryption

c,algorithm,security,math,encryption
I'm trying to reverse the following code in order to provide a function which takes the buffer and decrypts it. void crypt_buffer(unsigned char *buffer, size_t size, char *key) { size_t i; int j; j = 0; for(i = 0; i < size; i++) { if(j >= KEY_SIZE) j = 0;...

## C language, vector of struct, miss something?

c,vector,struct
This is a part of my program that I want to create a vector of struct typedef struct { char nome[501]; int qtd; int linha; int coluna; } tPeca; tPeca* criarPecas(FILE *pFile, int tam) { int i; tPeca *pecaJogo = (tPeca*)malloc(tam*sizeof(tPeca)); if (pecaJogo == NULL) return NULL; for (i =...

## scanf get multiple values at once

c,char,segmentation-fault,user-input,scanf
I need to get in one single shot different inputs from one single line. In particular I need to get a single char and then, depending on which char value I just read, it can be a string and an int or a string, an int and another string and...

## Disadvantages of calling realloc in a loop

c,memory-management,out-of-memory,realloc
I'm trying to implement some math algorithms in C on Windows 7, and I need to repeatedly increase size of my array. Sometimes it fails because realloc can't allocate memory. But if I allocate a lot of memory at once in the beginning it works fine. Is it a problem...

## execl() works on one of my code, but doesn't work on another

c,execl
I already used execl() in code, and it worked well. But this time, I really have no idea why it doesn't work. So here's the code that do not work #include <unistd.h> #include <stdio.h> int main() { int i = 896; printf("please\n"); execl("home/ubuntu/server/LC/admin/admin", (char*)i, NULL); printf("i have no idea why\n");...

## free causing different results from malloc

c,string,malloc,free
Below is a C program i have written to print different combination of characters in a string. This is not an efficient way as this algorithm creats a lot of extra strings. However my question is NOT about how to solve this problem more efficiently. The program works(inefficiently though) and...

## Galois LFSR - how to specify the output bit number

c,prng,shift-register
I am trying to understand how change the galois LFSR code to be able to specify the output bit number as a parameter for the function mentioned below. I mean I need to return not the last bit of LFSR as output bit, but any bit of the LFSR (...

## Passing int using char pointer in C

c,exec,ipc
I'm trying to figure out how to pass an int using a char pointer. It fails once the int value is too large for the char. This is what I'm trying to figure out: char *args[5]; int i = 20; /*some other code/assignments*/ args[2] = (char *)&i; execv(path, args); How...

## C binary tree sort - extending it

c,binary-tree,binary-search-tree
I need some help in C Help me to extend the binary tree sort on C. I need to return a sorted array in sort function. here it is: #include <stdio.h> #include <stdlib.h> struct btreenode { struct btreenode *leftchild ; int data ; struct btreenode *rightchild ; } ; void...

## Dynamic programming: how to design algorithm for when there are two factors to consider?

algorithm,optimization,dynamic-programming,frequency
I have the following problem and I only have a slight idea about it: Consider a tape storage problem. Given n files of length l1,...,ln and frequencies with which they are accessed f1,...,fn, where sum of all frequencies is 1 and 0<fi<1. "Optimal" means to minimize the average retrieval time...

## C++ / C #define macro calculation

c++,c,macros
Suppose I have #define DETUNE1 sqrt(7)-sqrt(5) #define DETUNE2 sqrt(11)-sqrt(7) And I call these multiple times in my program. Are DETUNE1 and DETUNE2 calculated every time it is called? Thanks. Please don't downvote this, I really want to know and a search didn't turn up anything definite. ...

## How can I align stack to the end of SRAM?

c,embedded,stm32,gnu-arm,coocox
I have a STM32F103VCT6 microcontroller with 48kb of SRAM, and recently i've got a memory collision: I have some static variable (lets call it A) located in heap with size of 0x7000 and I wrote some simple function to get info about stack and heap: void check(int depth) { char...

## How does ((a++,b)) work? [duplicate]

c,function,recursion,comma
This question already has an answer here: What does the comma operator `,` do in C? 8 answers In the below block of code, I am trying to understand how the line return reverse((i++, i)) is working. #include <stdio.h> void reverse(int i); int main() { reverse(1); } void reverse(int...

## Infinite loop with fread

c,arrays,loops,malloc,fread
I'm trying to allocate an array 64 bytes in size and then loop over the array indexes to put a read a byte each from the inputfile. but when I don't malloc() the array indexes, the loop stays in index0 (so each time it loops it replaces the content in...

## C programming - Confusion regarding curly braces

c,scope
The following code is for replacing multiple consecutive spaces into 1 space. Although I manage to do it, I am confused in the use of curly braces. This one is actually running fine: #include <stdio.h> #include <stdlib.h> int main() { int ch, lastch; lastch = 'a'; while((ch = getchar())!= EOF)...

## Loop through database table and compare user input

mysql,c
I am trying to loop through the rows in a MySql table and compare the data in a certain column to some user input using C. Currently my code looks like this: MYSQL *cxn = mysql_init(NULL); MYSQL_RES *result; unsigned int num_fields; unsigned int num_rows; char *query_string; MYSQL_ROW *row; if (mysql_real_connect(cxn,...

## How to give mathemarical proof or support my answer through reasoning as a general case?

algorithm
You are managing a software project that involves building a computer-assisted instrument for medical surgery. The exact placement of the surgical knife is dependent on a number of different parameters, usually at least 25, sometimes more. Your programmer has developed two algorithms for positioning the cutting tool, and is seeking...

## How to read string until two consecutive spaces?

c,format,sscanf,c-strings
A well known function of the scanf() functions is that you can pass a format to scan input according to this format. For my case, I cannot seem to find a solution searching this and this documentation. I have a string (sInput) as the following: #something VAR1 this is a...

## Algorithmic big o order of growth code

algorithm,discrete-mathematics
I'm doing an online course and i'm stuck on this question. I know there are similar questions but they don't help me. What is the order of growth of the worst case running time of the following code fragment as a function of N? int sum = 0; for (int...

## getchar() not working in c

c,while-loop,char,scanf,getchar
getchar() is not working in the below program, can anyone help me to solve this out. I tried scanf() function in place of getchar() then also it is not working. I am not able to figure out the root cause of the issue, can anyone please help me. #include<stdio.h> int...

## Understanding Big-Ω (Big-Omega) notation

algorithm,big-o
I was doing some reading on logarithms and the rate of growth of the running time of algorithms. I have, however, a problem understanding the Big-Ω (Big-Omega) notation. I know that we use it for 'asymptotic lower bounds', and that we can express the idea that an algorithm takes at...

## 3 X 3 magic square recursively

c++,algorithm,math,recursion
I'm trying to find all possible solutions to the 3X3 magic square. There should be exactly 8 solutions. My code gets them all but there are a lot of repeats. I'm having a hard time tracking the recursive steps to see why I'm getting all the repeats. // This program...

## OpenGL glTexImage2D memory issue

c,opengl
I'm loading a cubemap to create a skybox, everything is fine and the skybox renders properly with a correct texture application. However, I decided to check my program safety with valgrind, Valgrind gives this error: http://pastebin.com/seqmXjyx The line 53 in sky.c is: glTexImage2D(GL_TEXTURE_CUBE_MAP_POSITIVE_X + i, 0, GL_RGB, texture.width, texture.height, 0,...

## Should checking loop conditions be counted towards total number of comparisons?

c++,algorithm,sorting,c++11
I have implemented three different sorting algorithms and now I want to confirm that my approach of counting the total number of comparisons is correct. In my mind, the number of comparisons shouldn't be tied to the conditional branches because if the condition isn't met, the comparison was still made...

## How to control C Macro Precedence

c,macros
#define VAL1CHK 20 #define NUM 1 #define JOIN(A,B,C) A##B##C int x = JOIN(VAL,NUM,CHK); With above code my expectation was int x = 20; But i get compilation error as macro expands to int x = VALNUMCHK; // Which is undefined How to make it so that NUM is replaced first...

## Set precision dynamically using sprintf

c,printf,format-string
Using sprintf and the general syntax "%A.B" I can do this: double a = 0.0000005l; char myNumber[50]; sprintf(myNumber,"%.2lf",a); Can I set A and B dynamically in the format string?...

## What all local variables goto Data/BSS segment?

c++,c,nm
The man page of nm here: MAN NM says that The symbol type. At least the following types are used; others are, as well, depending on the object file format. If lowercase, the symbol is usually local; if uppercase, the symbol is global (external) And underneath it has "b" and...