generic module to add , subtract, mul 2 numbers of any size

[alokdube]

math can take a walk,
im trying this tonite. will let u know

[alokdube]

right now, im just trying to optimize my multiplication() library using a bit of ur code

lets see where i go

[pdwyer]

Or take a look at Michael Vogel's code, his multiply was faster I believe from the Project Euler stuff.

[alokdube]

that would be cheating paul both u and i know if we had a bit of money and some good micros with us, we could do it , strings or no strings citeseer papers or no papers

[pdwyer]

admitedly, the main reason for doing this was originally curiosity, otherwise I would have just gone and got some professional DLL.

The other thing I want to do eventually is to play with making a little lib for encryption key exchange like this http://en.wikipedia.org/wiki/Diffie-Hellman . The problem is that you need to be able to work with 1024 bit numbers etc , and MOD() very large numbers using primes.

I still don't have a function for generating large prime numbers but I'm getting closer (by that I mean, I occasionally have enough interest to be bothered ).

Thanks to your post I now have Div and Mod and two bugs out of subtract More pieces of the puzzel done!

It takes a post like this to rekindle my interest in something, then I dish out that old project and play with it a little more

[alokdube]

if ur going for DH i can assure u of atleast 25 good programmers, (i am algo guy) behind u!

[pdwyer]

25? I was kind of hoping it would be easy enough to do in an afternoon by myself if I had all the bits.

Or is that not what you mean?

[alokdube]

do ur thing!.... right now we can add, subtract, multiply, divide and get a mod
the rest is prime numbers, and DH already has a list of primes which they keep working on, and working against... so the rest is just faster computation..and how much u want to mess around
frankly, right now what i want to do is figure out why my strings code is not as tight, so i will borrow the multiply algo u posted across

[pdwyer]

if you have any loops which have len() (maybe left, right, mid) or concats strings is something you want to get rid of. PB has to traverse the length of the string to calculate it's length for a lot of it's string operations so the longer the string and the more times you call it, the greater the overhead.

I discovered this when I stumbed over the fact that for very large strings PB's findstring() was far inferior to powerbasic's instr(), as was len(). Powerbasic uses bstrs though that have the length as part of the structure so they don't need to look for the trailing null.

Calc len() once then hold it in another var and don't have things like

while len(string) > x

or

For i = 1 to len(string)

as these get calced every loop and kill the performance.

If the strings are tiny then it's probably not an issue however

[alokdube]

with ur code itself i can compute 2^1024 (ofcourse there are better ways)
num$="2"
For i=1 To 1023

num$=BigMultiply(num$,"2")
Next i
PrintN (num$)

[pdwyer]

There's a BigPow() function that will be quicker. It recurses and speeds things up quite a bit. And it's a single function call.

[alokdube]

will my high count code gives this too
17976931348623159077293051907890247336179769789423065727343008115773267580550096
31327084773224075360211201138798713933576587897688144166224928474306394741243777
67893424865485276302219601246094119453082952085005768838150682342462881473913110
540827237163350510684586298239947245938479716304835356329624224137216

after a few minutes though
look strings apart, i dont think they matter, i know my algo for multiplication is way off, but it does give an answer, and given time even i know i can optimize it .... but i could solve this in BASICA back in 1980s too in some dick head math contest

[Michael Vogel]

Hi alokdube,

I'm quite sure you are doing brilliant coding, I will just ask for thinking about some optimizations...

The procedures I did are calculating your power example within 50 milliseconds.

So if calculation time is (also) a factor for doing this math things, it could be that you will find some alternative ways (not only the one I implemented) to get the same results (but faster )

Code: Select all

; ~~~ 2^1024 ~~~
a=GetTickCount_()
power.VNF
PutNumber(@"1",power)
n=1024
While n
	VNFmuw(power,2,power)
	n-1
Wend
a-GetTickCount_()
MessageRequester(Str(a),Number(power))

To be honest, I am no progamming guru - so the division routine is one point, where I failed to do find a faster approach

Michael

[alokdube]

well my entire code is totally irrelevent, i was just trying the algo, and paul has done a great job in helping me get better answers,

the division code is what i was working around, hence all those funny routines around it...
the target was to be able to divide 2 large numbers... and this seems to work just as well, though i admit my multiplication algo is way way off

[pdwyer]

The "trick" for optimizing is to collect ciphers into groups so it can be handled faster...

Thats easy for add/sub/mul, for example:
123456 x 123456 can be done with doing 36 multiplications (1x1, 1x2, 1x3,... 6x6) and quite a lot of additions - which costs a lot of time.
But if grouped, let's say into pieces with three ciphers, you only have to do 4 multiplications: 123x123, 123x456, 456x123 and 456x456 - that should be already about 10 times faster!

I played around to find a large number of cipher which can be handled without problems, using quads at the beginning but returned to long variables which are able to work with numbers up to +/-2.000.000.000 - this allows to collect even 9 ciphers to a single group and have space for the "overflow" when adding two of these numbers.
So that gives an enormous boost to the calculating procedures and I'm quite happy about this

The most important problem (at least for me) is to find a routine to divide numbers using these groups!
All I was able to do for now is programming a (simple) division routine, which is used when the divisor is smaller than 1x10^10...

Michael

I didn't think of doing it that way... I guess it would be a lot faster but the code would be a little harder to write first time round (while you get your mind around the issues). For division, the PDF link I posted shows a way to do what you want to do using 3 digits at a time in 16bit words. I didn't go into depth trying to understand it as I was still wanting to see if my recursion function would work.

I haven't been back to the Euler site for a while, I got to about 14% but then the it started getting too difficult for me in that I could no longer understand what the question was asking My high school dropout math level was coming back to haunt me I think.

It was a lot of fun though