Hello everybody,

at the moment I'm working on an assembler bignum libary for a schoolproject.
I have to support numbers up to 1024 bit and to implement all basic arithmetic operations. So far I had a lot of fun coding this and I've learnt a lot :-)

However, now I'm at a point where I need a helping hand please.
I'm trying to code a function which I named: IsDivideable(a,b)
This function has to test if bignumber a is perfect divideable by bignumber b.
At the moment I solve this task by calculating a mod b and then I check if the reminder is null. This works quit good but I found that it is very slow...

Now my question is: As i dont really need the reminder (I just want to know if its null -> divideable) is there maybe a faster algorithmn known? Or is there maybe a completly different way to check if a bignum is perfect divideable by another bignum?

Thanks for your help.
Posted on 2003-11-29 08:05:27 by tuzla
There is another approach to mod:

e.g. you want to test IsDivisible(3456163461354669554662454,1335261335)
You can take first 11 digits of n1 and find mod of it:
34561634613 mod 1335261335=1180101238
replace first 11 with this mod
118010123854669554662454
find first (len(1335261335) in this case 10)+1=11digits again and repeat
11189217054669554662454
507126374669554662454
13079680719554662454
1062328704554662454
127645770054662454
7472249904662454
128312562162454
8139042012454
127474002454
7300482304
reminder:624175629

This may be done recursively also IMO

I don't know if this is faster, just an opinion
Posted on 2003-11-29 09:30:30 by inFinie