BigInt module (SSE2)

[AZJIO]

Can this module be made available in SpiderBasic? I used this in a password generator and would like the program to be available on the phone.

[mk-soft]

No,

its intel assembler code. No java or no arm processors ...

[jack]

doesn't javascript have a bigint type?
I say this because of https://pi-calculator.netlify.app/
it works offline in the browser

[AZJIO]

There is a BigNum library on AutoIt3, it generally works with a string. That is, it performs step-by-step calculations, and the result is written to a string. It works slowly, but it works. I would like it to be possible to get even a slowly working, but the same result. On asm it works instantly, on AutoIt3 - half a second. But this is not critical for my program.

[Al_the_dutch]

Thx for all the great work. I ran into the problem that I get unexpected results. Can anyone help? Thanx!

Code: Select all

IncludeFile("..\bigint.pbi")

UseModule BigInt

EnableExplicit

Procedure Hex2Dec(hex$)
   ProcedureReturn Val("$"+hex$)
EndProcedure

; http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm
Define.BigInt h1, h2, h3, h4, h5, h4_hex$

SetValue(h1, 9)
SetValue(h2, 27)
 
Debug "Modulus Exponentiation: 9 ^ 27 mod 27 = 3*9, I expect 0 but get 20?!"
ModPow(h4, h1, h2, h2)
h4_hex$ = GetHex(h4)
Debug "ModPow(h4, 9, 27, 27) = " + Hex2Dec(h4_hex$)

SetValue(h1, 9)
SetValue(h2, 81)

Debug "Modulus Exponentiation: 9 ^ 81 mod 81 = 9*9, I expect 0 but get 72?!"
ModPow(h4, h1, h2, h2)
h4_hex$ = GetHex(h4)
Debug "ModPow(h4, 9, 27, 27) = " + Hex2Dec(h4_hex$)

End; EndItAll

[Little John]

Thx for all the great work. I ran into the problem that I get unexpected results. Can anyone help? Thanx!

Unfortunately, you did not write what PB version and what operating system you used when you got those results.

I tested your above code with PB 6.00 LTS (x64) and PB 6.01 beta 4 (x64) on Windows 11, and I always got the result "0", as expected.

BTW:
Near the end of your code, it reads
Debug "ModPow(h4, 9, 27, 27) = " + Hex2Dec(h4_hex$)
but it should be
Debug "ModPow(h4, 9, 81, 81) = " + Hex2Dec(h4_hex$)

[Al_the_dutch]

Both good points. I use PureBasic 6.00 LTS (Windows - x64) on Windows 10 Home... Strange!

CPU: Intel(R) Core(TM) i7-5820K CPU @ 3.30GHz 3.30 GHz

Some more searching: I get the expected zero's with
#BigIntBits = 512; not with 2048
in BigInt.pbi. It was on 2048, a multiple of 512.

[Little John]

Yes, that's strange.
I used Wilbert's code as is in the first post of this thread, i.e.
#BigIntBits = 2048.

CPU: Intel(R) Core(TM) i5-1035G4 CPU @ 1.10GHz 64 bit

[Al_the_dutch]

The problem only seems to be on my PC with #BigIntBits = 2048, I tried 512,1024 and 4096 without a problem.
You even don't have a problem with #BigIntBits = 2048 and we both use Windows x64.
I wonder if there's anyone who knows the possible reason for it. But I am fine now, I have a workaround. Thx!

[Al_the_dutch]

I did a test with many calculations and compared the output between runs with 512,1024, 2048 and 4096 as #BigIntBits. All were the same with the exception of 2048 on many cases. As long as nobody has an explanation, I would suggest that if you use BigInt, you compare the output with the output using another #BigInts to be sure that this issue don't effect your situation. Above all I am happy to be able to use BigInt!

[wilbert]

Unfortunately I also haven't got a clue.
Does this happen only with ModPow or also with ModMul ?

[Al_the_dutch]

Thx wilbert.
I did not use ModMul, so I wrote a tester with it and I did not get any differences in a wide range between running with #BigIntBits 2048 and 4096.
I also tested with 216*46656 mod 9 = 6^9 mod 9 should be 0 and it is. With ModPow 6^9 mod 9 and #BigIntBits 2048 it gives not 0 on my PC.
So the problem seems only related to ModPow with #BigIntBits 2048 on my PC. I am almost thinking it might be a specific CPU problem.
@wilbert, what is the influence of #BigIntBits in general?

[wilbert]

So the problem seems only related to ModPow with #BigIntBits 2048 on my PC. I am almost thinking it might be a specific CPU problem.

Unfortunately I don't know since I can't reproduce the problem.

@wilbert, what is the influence of #BigIntBits in general?

It determines the amount of bits for a number.
The two biggest native types PB supports are 32 and 64 bit numbers.
When you set #BigIntBits to 512, it's 512 bit numbers etc.
The bigger values for #BigIntBits you choose, the slower it will be.

[AZJIO]

Can you adapt to version 6.03?
*vn -> vn3 ?

[wilbert]

Can you adapt to version 6.03?
*vn -> vn3 ?

Try moving the *vn declaration inside the divmod_private procedure to the line above like this.

Code: Select all

    Protected.BigInt un, vn, *vn
    Protected.i qhat, rhat, *un.Quad