Guide me, writing Big Num Math functions.. [Archive]

View Full Version : Guide me, writing Big Num Math functions..

evaluator

May 10th, 2015, 09:32

Hello, all!

for fun, I started writing of simple Math functions for Big Nums.. (ADD, SUB, NEG, MUL, DIV, SHL, SHR).
Now I want to know how good and fast are they.

So, here I want your guide. give me info about available code-modules, so I will test and compare their speed with my.
hope, there is some BigNum DLL...
(yo, looks like lamer search request, but bear with me)

better, just preform speed test..
here are my speeds. look in ZIP

[removed fake RDTSC]

just checked & my RDTSC reports false speed at 4Ghz (because of overclocking). But it is on 3.33GHZ.
so here are timings:

Code:

A=B= (2^524288) -1 // in BITNUM

A MUL B = C

; Time =   0.875 sec



then, 

C DIV B = A

; Time = 20.875 sec





A4=B4= (2^2097152) -1 // in BITNUM

A4 MUL B4 = C4

; Time = 13.797 sec



then, 

C4 DIV B4 = A4

; Time = 333.719 sec



CPU 3.33ghz

I ran test on other not-overclocked 1.5 GHZ CPU, so it shows more reliable RDTSC

Code:

**************************

CPU 1.5ghz



A=B= (2^524288) -1 // in BITNUM

A MUL B = C

; Time =   1.591 sec

; RDTSC = 2,379,654,669



then, 

C DIV B = A

; Time = 44.054 sec

; RDTSC = 65,912,884,416 



*

*

A4=B4= (2^2097152) -1 // in BITNUM

A4 MUL B4 = C4

; Time = 25.412 sec

; RDTSC = 38,009,393,646 



then, 

C4 DIV B4 = A4

; Time = 708.693 sec

; RDTSC = 1,060,613,423,675

EDIT:
I just read some docs, so I coded simple or basecase kind of algos..

EDIT:20150531
today finished SQR square procedure. It is 1.87x faster then MUL.
But in docs written, it can be 1.5x faster.
either my MUL is bad, or SQR is so good.

BanMe_2

May 10th, 2015, 10:15

Took me too long to understand... :[ sorry for the initial doubt.

https://gmplib.org/
http://gmc.yoyogames.com/?showtopic=454894

investigate gnomehome on masm32.

FoxB

May 10th, 2015, 10:40

i'm use PolarSSL ("https://tls.mbed.org/download/start/mbedtls-1.3.10-gpl.tgz") - bignum ("https://github.com/polarssl/polarssl/blob/master/library/bignum.c")

BanMe_2

May 10th, 2015, 13:07

http://www.leemon.com/crypto/BigInt.js

evaluator

May 10th, 2015, 13:50

thank you for help..
but I can do nothing with sources.. that is why I ask for your help.

if you are giving DLL, then I should know howto call..

but better help will, if you can just measure speed of calculation. here are my speed results in attachments

BanMe_2

May 12th, 2015, 22:00

I wish, I could understand you better... and get a finer grain of detail from your broad strokes of words.

You either want a dll to compare and test big number function against you own, or you want a test harness to to measure execution time of comparable functions across different modules.

I am lost in the words.

please clarify.
regards

evaluator

May 13th, 2015, 13:32

best for me: perform same calculations (which I did, see MUL_ANY.ZIP) and report timings.

evaluator

May 14th, 2015, 12:24

updated first post with other CPU values.

BanMe_2

May 20th, 2015, 20:32

Sorry to not have anything to forward the discussion along, but how did you accomplish the task of dealing with large numbers? I would like to try to understand how you went about it.

"basecase", lead to D&C algos is this the avenue you took?

evaluator

May 22nd, 2015, 03:20

em, basecase means simple methods, as we did learn in school. I am not math-man, so cant do D&C theories.

Large numbers are treated just as many dwords & cycles of MUL,ADD,ADC heppens.
Except DIVISION.

BanMe_2

May 26th, 2015, 14:46

http://www.geeksforgeeks.org/divide-and-conquer-set-2-karatsuba-algorithm-for-fast-multiplication/
http://www.stoimen.com/blog/2012/05/15/computer-algorithms-karatsuba-fast-multiplication/

difference between you and math person is only time and study

kind regards.

evaluator

May 31st, 2015, 06:59

well, briefly those algos are described in GMP help files.
actually I am interested, how good I wrote basic algos.

BanMe_2

June 16th, 2015, 19:31

I am really trying to figure out how to interpret the string as a actual number..this is bugging the hell out of me. Ive even thought of doing a webgl chinese sticks version.

once I get a actual number to represent the string(s) I can then divide that number by the exact amount of places it is above the decimal point to shrink it below the decimal point then perform the calculation in 1 step and reconstitute the results afterward.