I'm trying to write a HugeMotherFuckingInt processing library in C.
My first try, I stored the numbers as a char[] and computed them using basic arithmetic.
My second try, I stored the numbers as unsigned long char[]. This proved to be a faster, easier and clearer approach.
Still though, it seems to be a bit too slow.
What other data structures might result in faster execution of basic arithmetic +/*-?
Also, are there any algorithms to speed up the arithmetic operations themselves?
Name:
Anonymous2011-08-15 8:18
unsigned long char[]
Actually, I meant an unsigned long int[].
Name:
n3n7i2011-08-15 8:25
=) been there... 360 Digit -Base 10- Reporting in
You should be using at least int's [4 byte per array pos].... thats 0 - 4294967296 as unsigned // just use signed ints (Max ~2000000000) and Use BASE 1,000,000,000 [Largest/Easiest fit](10^n is just nicest to use... 2^n if you like)
Leaving at least one bit spare - lets you add two arrays together plus carry the ones
And have your arrays set up (Big / Little?? Endian) lowest base first (Whichever-really=) - I think lowest is nicer cos you can run your loops from element 0... An stitch 'em up
You should use an unsigned int representation for efficiency as this is the machine word size. C ensures unsigned addition wraps around so you can implement most algorithms quite easily. Some tricks are needed for multiplication which aren't worth discussing. Endianness doesn't really matter.
typedef struct _biginteger {
int length;
int capacity;
unsigned int* data;
} bigint;
If you are actually planning to use the library rather than write a toy implementation you should just use an existing implementation, eg GMP.
Unless you have ~500 limb integers long multiplication will probably be the fastest method available- so any performance improvements need to come from micro optimizations. Or rather, hand coding assembly, which is why you don't really want to write your own.
>unsigned addition wraps around C1X 6.2.5 : 9
Woah I was so sure of C having obscure arcane rules for both signed and unsigned addition operators that I never bothered to check until now.
I guess the committee realized that some times the best way to introduce arbitrary retardation is to inject bits of sanity at random.
Name:
Anonymous2011-08-15 20:08
I'm also making a toy big integer library.
I was wondering what's an efficient way to divide integers.
Most of the methods I've come across involve inversion of the denominator but I'm not interested in decimal places of arbitrary precision.
Name:
n3n7i2011-08-15 22:24
Can make a pretty fast modulo style divide...
-Just use the multiply trick (above)-
Here's where i got up to last night... (before it got too cold to code at least..)
//-------------------------------
#include <stdio.h>
#include <stdlib.h>
const RRay = 50; // Max array Size //
const CutOff = 1000; // Base
int aa[52]; int ab[52]; int ac[52];
//----------------------------------
void Add(int xa[], int xb[]){
int i, iCarry=0, raymax=0;
void Set(int xa[], int xb[]){
int i;
for(i=0;i<=RRay;i++) xa[i] = xb[i];
}
//----------------------------------
int GOWFish(int a, int b){
int ret=0;
if(a!=b){
if(a>b) ret= 1;
if(a<b) ret=-1;
}
return ret;
}
//---------------------
int GreaterOrWhat(int xa[], int xb[]){
int a, b, i, ret=0;
a = xa[RRay];
b = xb[RRay];
i =a+1;
ret = GOWFish(a, b);
while((ret==0) + (i>=0)==2){
i--;
a = xa[i];
b = xb[i];
ret = GOWFish(a, b);
}
return ret;
}
//----------------------------------------------
void Add(int xa[], int xb[]){
int i, iCarry=0, raymax=0;
>>14-15
You don't need any ``kewl trix'' for subtraction, it is addition with the second operand's sign bit flipped. Use unsigned ints and keep a sign bit.
>>17
They aren't. In C, if a signed int overflows, it's undefined behaviour, unsigned ints are guaranteed to wrap around (>>9), so you can portably check for overflow. You're wasting one bit for each limb, which is worse than the 7 bits wasted to store the sign bit (that can be reused for some other flags, unlike the integers' sign bit), to store redundant information, reducing the length of each limb. Unsigned integer operations are also usually faster than signed one.
Also, please, learn to properly (read: not randomly) capitalize words, link to posts you're responding to, and drop the emoticons and the name (this is an anonymous programming textboard, and that's what made /prog/ great).
Name:
n3n7i2011-08-16 2:11
...i Don't know Knuth, so I can't really say
...Yes it's ugly [u can make it pretty if u want ;]
...Its being caught before it wraps (Hence no prob) // 30 out of 32 bit aint bad?
...Anything Else?
>>23
If 31 out of 32 is bad, 30 out of 32 is doubly bad. Good enough is enemy of better, which is enemy of perfect.
Even if it is a toy implementation, you should do it properly.
And, again, proper grammar and punctuation, please.
I guess i should point out i'm using signed ints (Obv) to make a 'HugeUnsignedInt' .... (Not-so-Obv)
...If you actually tried to make one of these on your own (Without just copy-pasta-ing it) you might see some wisdom in them codes....
Its less than a days work.... of course its ugly...(keep in mind i have written one of these b4 // have an idea of the problems/ some solutions? already /// wasn't so fAST the first time around)
...Search / Replace would clean it up easy enough??
>>28 i'm using signed ints [...] to make a 'HugeUnsignedInt'
And I even thought you couldn't get worse!
Seriously, that's retarded, it should be rewritten from scratch to clean it up.
>>28
I can insure you both me and the Sussman have implemented multiple precision libraries. Would you leave us be?
Name:
n3n7i2011-08-16 4:31
Your using unsigned int >> signed int
Im using signed int >> unsigned int
Really they are not so dissimilar... Synergetic even....
Perhaps i only need Unsigned Big Numbers? El-Gamal and the like don't use anything below zero....
No, I'm using unsigned+sign bit, and there's a reason for it (unsigned ops are faster, 1 bit wider, etc).
You have no reason to make unsigned bigints from signed ints: you waste space, it's slower, it's stupid.
I mean, what's next, 32 bit numbers using bigints?
...perhaps storing highest used base a la XRAY[50] for quick Greater-than eval / Saving a few loop Reps here and there /// was a bit too advanced / Unclear?
+I spy a memory / speed tradeoff or two? //More spare bits is equiv to larger max addition ops (Instead of just two // add 4 or even 8 bigvals at once [2-3bit tradeoff's]).....
>>33
Uints wrap around, unsigned addition always yields something >= to the greater operand, so you can check for unsigned overflow with c = a + b; c < max(a,b) // true = overflow. Also, the architecture is likely to have a carry flag and an add-with-carry instruction.
>>34
>=, >, <, <= are implemented by just comparing the sign bits, if equal compare last valid index of the bigint vectors (because you store the length), and if equal compare the last elements. No loops involved.
I haven't read your code because it's absolute shit. Learn to program, then come back.
Also, what the fuck are those slashes?
>>36
You mean c <= a (think of a+0, even though you probably do nothing on addition to 0)? You're right, though, I was just being lazy and didn't want to check if that could work.
Name:
n3n7i2011-08-16 7:01
...It's working again =)
Anyone Got some big (Hopefully easy to enter) Numbers?
eg 1, 1, 1, 1, is Equiv to 1, 000,000,001, 000,000,001, 000,000,001