unsigned 64 bit functions

Forum 2005-2010 (read only) General Exhibition
1

the standard 64 bit math brings in about 5000 bytes and it is all pass by value (8 bytes apiece plus some shifting about). This takes my current project beyond the 14k boundry.

these functions bring in 1214 bytes(I think), and everything is pass by reference
I don't know how fast they are, don't need superfast for my current app.
compared to the LCD pauses, performance probably isn't a big deal,
and I get to stop worrying about scaling my 32 bit functions with a bunch of conditionals :slight_smile:

64 bit numbers are represented as an array of length 2 , [0] is most significant.
I chose array because it is pass by reference and didn't have to make a new type in arduino
also hoping the bits are in contiguous memory if an optimized version materializes

yah, it could be a library, but current project is intended to be simple cut and paste, minimal fuss on the end user. yah there could be more functions, but these are just what I needed and space is already at a premium.

//realized by Dave Brink
unsigned long zero64[]={0,0}; //just for comparisons sake

void init64(unsigned long  an[], unsigned long bigPart, unsigned long littlePart ){
  an[0]=bigPart;
  an[1]=littlePart;
}

//left shift 64 bit "number"
void shl64(unsigned long  an[]){
 an[0] <<= 1; 
 if(an[1] & 0x80000000)
   an[0]++; 
 an[1] <<= 1; 
}

//right shift 64 bit "number"
void shr64(unsigned long  an[]){
 an[1] >>= 1; 
 if(an[0] & 0x1)
   an[1]+=0x80000000; 
 an[0] >>= 1; 
}

//add ann to an
void add64(unsigned long  an[], unsigned long  ann[]){
  an[0]+=ann[0];
  if(an[1] + ann[1] < ann[1])
    an[0]++;
  an[1]+=ann[1];
}

//subtract ann from an
void sub64(unsigned long  an[], unsigned long  ann[]){
  an[0]-=ann[0];
  if(an[1] < ann[1]){
    an[0]--;
  }
  an[1]-= ann[1];
}

//true if an == ann
boolean eq64(unsigned long  an[], unsigned long  ann[]){
  return (an[0]==ann[0]) && (an[1]==ann[1]);
}

//true if an < ann
boolean lt64(unsigned long  an[], unsigned long  ann[]){
  if(an[0]>ann[0]) return false;
  return (an[0]<ann[0]) || (an[1]<ann[1]);
}

//divide num by den
void div64(unsigned long num[], unsigned long den[]){
  unsigned long quot[2];
  unsigned long qbit[2];
  unsigned long tmp[2];
  init64(quot,0,0);
  init64(qbit,0,1);

  if (eq64(num, zero64)) {  //numerator 0, call it 0
    init64(num,0,0);
    return;            
  }

  if (eq64(den, zero64)) { //numerator not zero, denominator 0, infinity in my book.
    init64(num,0xffffffff,0xffffffff);
    return;            
  }

  init64(tmp,0x80000000,0);
  while(lt64(den,tmp)){
    shl64(den);
    shl64(qbit);
  } 
  
  while(!eq64(qbit,zero64)){
    if(lt64(den,num) || eq64(den,num)){
      sub64(num,den);
      add64(quot,qbit);
    }
    shr64(den);
    shr64(qbit);
  }

  //remainder now in num, but using it to return quotient for now  
  init64(num,quot[0],quot[1]); 
}


//multiply num by den
void mul64(unsigned long an[], unsigned long ann[]){
  unsigned long p[2] = {0,0};
  unsigned long y[2] = {ann[0], ann[1]};
  while(!eq64(y,zero64)) {
    if(y[1] & 1) 
      add64(p,an);
    shl64(an);
    shr64(y);
  }
  init64(an,p[0],p[1]);
} 

void setup(){ 
  
  Serial.begin(9600);
  unsigned long a1[]={0x2,0xFFFFFFFF};
  unsigned long a2[]={0x0,0x0FFFFFFF};
  prt(a1);
  mul64(a1,a2);
  prt(a1);
  div64(a1,a2);
  prt(a1);
  init64(a2,a1[0],a1[1]);
  div64(a1,a2);
  prt(a1);

}
void loop(){}

void prt(unsigned long  an[]){
  Serial.print(an[0],HEX);
  Serial.print(" ");
 Serial.println(an[1],HEX);
}
2

hi dcb, i was interested in yr comment so tried the following code to see how much flash it used:

long long LL1,LL2;
LL1 = Serial.available();
LL2 = LL1<< Serial.available();
Serial.print((long)LL2);
Serial.print("size of long long is ");
Serial.println(sizeof(LL2));

this code added around 500 bytes. The serial output does confirm that a long long is 8 bytes.

3

Hmm.. You apparently have to do something interesting with the longs before it happens, i.e. the following code compiles to 5734 bytes:

unsigned long long x = 1ull;
unsigned long long y = 1ull;
unsigned long long z = 1ull;
void setup(){
  x=y*z;
  x=y/z;
  x=x+z;
  x=x-z;
  x<<=2;
  x>>=2;
}

void loop(){}

edit: it is 2462 bytes if you comment out the divide line.

4

Division involving longs brings in a lot of code, so I can imagine that division involving long longs would be huge. It's probably worth it to work around division involving long longs, or to implement your own smaller but slower solution like you have above.

  • Ben
5

I was doing some performance testing and am now confused :slight_smile: This bloating of the generated script might be a glitch after all, the code below compiles to 4540 bytes and has all kinds of junk in it ?!? Whereas the trivial example in reply 2 is 5734 bytes.

Here's the performance info for the homemade version
About 1.1 milliseconds for division
about 0.6 milliseconds for
about .01 milliseconds for addition and subtraction.

The built in math did not even register in milliseconds.

So I have a workaround for now, but maybe this belongs on the bugs/suggestion board. If a moderator deems that appropriate then please relocate this thread.

unsigned long zero64[]={0,0};

void init64(unsigned long  an[], unsigned long bigPart, unsigned long littlePart ){
  an[0]=bigPart;
  an[1]=littlePart;
}

//left shift 64 bit "number"
void shl64(unsigned long  an[]){
 an[0] <<= 1; 
 if(an[1] & 0x80000000)
   an[0]++; 
 an[1] <<= 1; 
}

//right shift 64 bit "number"
void shr64(unsigned long  an[]){
 an[1] >>= 1; 
 if(an[0] & 0x1)
   an[1]+=0x80000000; 
 an[0] >>= 1; 
}

//add ann to an
void add64(unsigned long  an[], unsigned long  ann[]){
  an[0]+=ann[0];
  if(an[1] + ann[1] < ann[1])
    an[0]++;
  an[1]+=ann[1];
}

//subtract ann from an
void sub64(unsigned long  an[], unsigned long  ann[]){
  an[0]-=ann[0];
  if(an[1] < ann[1]){
    an[0]--;
  }
  an[1]-= ann[1];
}

//true if an == ann
boolean eq64(unsigned long  an[], unsigned long  ann[]){
  return (an[0]==ann[0]) && (an[1]==ann[1]);
}

//true if an < ann
boolean lt64(unsigned long  an[], unsigned long  ann[]){
  if(an[0]>ann[0]) return false;
  return (an[0]<ann[0]) || (an[1]<ann[1]);
}

//divide num by den
void div64(unsigned long num[], unsigned long den[]){
  unsigned long quot[2];
  unsigned long qbit[2];
  unsigned long tmp[2];
  init64(quot,0,0);
  init64(qbit,0,1);

  if (eq64(num, zero64)) {  //numerator 0, call it 0
    init64(num,0,0);
    return;            
  }

  if (eq64(den, zero64)) { //numerator not zero, denominator 0, infinity in my book.
    init64(num,0xffffffff,0xffffffff);
    return;            
  }

  init64(tmp,0x80000000,0);
  while(lt64(den,tmp)){
    shl64(den);
    shl64(qbit);
  } 
  
  while(!eq64(qbit,zero64)){
    if(lt64(den,num) || eq64(den,num)){
      sub64(num,den);
      add64(quot,qbit);
    }
    shr64(den);
    shr64(qbit);
  }

  //remainder now in num, but using it to return quotient for now  
  init64(num,quot[0],quot[1]); 
}


//multiply num by den
void mul64(unsigned long an[], unsigned long ann[]){
  unsigned long p[2] = {0,0};
  unsigned long y[2] = {ann[0], ann[1]};
  while(!eq64(y,zero64)) {
    if(y[1] & 1) 
      add64(p,an);
    shl64(an);
    shr64(y);
  }
  init64(an,p[0],p[1]);
} 

  unsigned long a1[]={0x2,0xFFFFFFFF};
  unsigned long a2[]={0x0,0x0FFFFFFF};
  unsigned long a3[]={0x0,0x0FFFFFFF};

  unsigned long long b1 = 0x2FFFFFFFFull;
  unsigned long long b2 = 0x0FFFFFFFull;
  unsigned long long b3 = 0x0FFFFFFFull;


void setup(){ 
  
  Serial.begin(9600);
  unsigned int loopcount=6000;

  unsigned long t = millis();
  for(unsigned int x = 0; x < loopcount; x++){
    init64(a1,0x2,0xFFFFFFFF);
    init64(a2,0x0,0x0FFFFFFF);
    div64(a1,a2);
  }
  Serial.println(millis()-t);  
  
  t = millis();
  for(unsigned int x = 0; x < loopcount; x++){
    b1 = 0x2FFFFFFFFull;
    b2 = 0x0FFFFFFFull;
    b3 = b1/b2;
  }
  Serial.println(millis()-t);  
  
  t = millis();
  for(unsigned int x = 0; x < loopcount; x++){
    init64(a1,0x2,0xFFFFFFFF);
    init64(a2,0x0,0x0FFFFFFF);
    mul64(a1,a2);
  }
  Serial.println(millis()-t);  
  
  t = millis();
  for(unsigned int x = 0; x < loopcount; x++){
    b1 = 0x2FFFFFFFFull;
    b2 = 0x0FFFFFFFull;
    b3 = b1*b2;
  }
  Serial.println(millis()-t);  
  
  t = millis();
  for(unsigned int x = 0; x < loopcount; x++){
    init64(a1,0x2,0xFFFFFFFF);
    init64(a2,0x0,0x0FFFFFFF);
    add64(a1,a2);
  }
  Serial.println(millis()-t);  
  
  t = millis();
  for(unsigned int x = 0; x < loopcount; x++){
    b1 = 0x2FFFFFFFFull;
    b2 = 0x0FFFFFFFull;
    b3 = b1 + b2;
  }
  Serial.println(millis()-t);  
  
  t = millis();
  for(unsigned int x = 0; x < loopcount; x++){
    init64(a1,0x2,0xFFFFFFFF);
    init64(a2,0x0,0x0FFFFFFF);
    sub64(a1,a2);
  }
  Serial.println(millis()-t);  
  
  t = millis();
  for(unsigned int x = 0; x < loopcount; x++){
    b1 = 0x2FFFFFFFFull;
    b2 = 0x0FFFFFFFull;
    b3 = b1 - b2;
  }
  Serial.println(millis()-t);  

  
  
  
  prt(a1);
  Serial.print((unsigned long) b3, HEX);

}
void loop(){}

void prt(unsigned long  an[]){
  Serial.print(an[0],HEX);
  Serial.print(" ");
 Serial.println(an[1],HEX);
}