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
find first (len(1335261335) in this case 10)+1=11digits again and repeat

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