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.

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.

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

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