Big Integer Package

[gnomehome]

I am a beginning masm32/intel assembly developer, but a quite experienced c/c++ developer.

That being said, I have been thinking about trying to write a big integer package (like for example GNU MP on UNIX) in assembly. I would need to implement functions like add, subtract, multiply and divide, how would I go about starting a project like this? Since the final product will be a dll, and I can't obviously start my beginning development and experimentation using a dll, should I use the sample code provided in the "Console Input/Output" thread, and start from there?

Also, I'm trying to figure out how to work with an integer, say for example 1024 bits in length using the 4 32-bit general purpose registers? (EAX, EBX, etc)

Thanks for any tips, suggestions, or warnings...

gh

[roticv]

Hello I am working on it, but currently not much progress. I only have multiplication, addition and subtraction up. Maybe we could join forces or something.

[thomasantony]

Hi,
  I am not very knowledgeable abt this. You will need to have 32 DWORD sized registers. So you can use and reuse the six registers ( EAX, EBX, ECX, EDX ESI EDI) or maybe use EBP too without using local variables.

Thomas :U

[raymond]

gnomehome

I don't know what your ultimate goal is regarding maximum size of numbers, input/output format of the numbers, complexity of the functions to be implemented, speed of execution, etc.

Have you given any thought to the use of BCD math if such would be satisfactory for all your goals. If you are not yet familiar with that subject, you may want to have a glance at the following (although it is still not yet fully completed):

http://www.ray.masmcode.com/BCDtut.html

Raymond

[Mark Jones]

You could indeed start the project as a DLL. You'd just need to code two programs - one for the DLL, and a second "testbed" app to call functions from the DLL. See the Iczelion Tutorial #17 for an example how to create and call functions from a DLL.

Debuggers are a godsend in Win32 assembly. You could also write the initial app as a typical MASM32 executable and step through the code. OllyDbg is great for this. But it might be more convenient to just add some edit boxes and buttons and create a real [ugly] application, then once working, rip out that code and build it into the DLL as per above.

As for handling the numbers themselves, it seems like you'll have to put the bits into a memory buffer, then develop a routine to treat the memory location as a "number." That way you're not trying to cram all those bits into active registers. I'm sure one of us can whip up something to get you started. Which brings me to question, what exactly are you trying to achieve with a "big-number" DLL? How important is speed? Are the values signed integers or float? Is the FPU's 80-bit REAL10 floating-point representation insufficient? Raymond's FPU page gives some great info and tools for MASM32 FPU usage. :)

[rea]

By the way, for the DLL I suguest you load/unload manually, in taht way, you only need to recompile the dll and not the two sources, for example, you can have a "test button" it load, test and then unload, in that way, when you recompile there not will be problem that the DLL cant be created.

You will only need rebuild the test program when you need add test for other routine...

[gnomehome]

Wow, I didn't expect to get this many replies so fast!

The package is intended for use in large prime based cryptography, so yes, speed is a factor.

That is a good idea using a chunk of memory, I've read about pointer registers, does that mean I can use it to point to the memory chunk? Or, would I need to treat the huge number in chunks, dealing with the first 32 bits, then taking the carry from that, and adding it to the next 32 bits, and etc?

Thanks for everything so far!

<edit>
Floating point is not necessary, all I need is integers.

Also, the only functions that would need be implemented at first are add, subtract, divide, and multiply.

I am unsure as per the maximum length of the number but I would assume something between 1024 - 4096 bits.
</edit>

[tenkey]

That is a good idea using a chunk of memory, I've read about pointer registers, does that mean I can use it to point to the memory chunk? Or, would I need to treat the huge number in chunks, dealing with the first 32 bits, then taking the carry from that, and adding it to the next 32 bits, and etc?

You pretty much need to treat the huge number in chunks.

[thomasantony]

Hi,
   With the advent of 64-bit pentiums, you can do it in bigger chunks (64-bit)

http://www.thetechzone.com/?m=show&id=199
http://www.intel.com/products/processor/pentium4/


Thomas :U

[roticv]

Thomas, You can use mmx/sse to do bigger chunks.

gnomehome, what do you think of my proposal? I can send you my code for you to take a look.

[gnomehome]

Roticv: I'd appreciate it.

Thomasantony: I have a dual opteron system, so I know this, but I am specifically working on a 32-bit system.

Thanks all :)

[gabor]

Hi!

That's a pitty that this thread has died. I am looking for extra large integer divide (the other 3 operations are really easy to implement). I found some other threads dealing with the division, so here I want to post a remark only.
I am a bit confused why are posts added about using 64bit regs or the 128bit regs of SSE. What is with 1024bit numbers? I think it is pretty clear that the problem here is not the size of available registers but the general methods of large integer arithmetics.

Greets, Gábor

[Rockoon]

I would do division with a binary search... but then I really don't know much about this subject

My strategy would require 0.5 * log2(n) bigmuls (give or take)


Perhaps there is a trick to calculating 1/n in decent time, turning it into a multiplication problem.

[hutch--]

Gabor,

I think Ray's suggestion of using BCD is probably the right one with very large numbers as it does not suffer register size limitations.

[Ratch]

gnomehome,

Also, I'm trying to figure out how to work with an integer, say for example 1024 bits in length using the 4 32-bit general purpose registers? (EAX, EBX, etc)

    You are talking about multiple-precision or modular arithmetic.  Your best bet for starters is to read The Art of Computer Programming, Volume 2/Seminumerical Algorithms  by Donald E. Knuth.  Here he gives the theory and psuedo-code for the four common arithmetic operations.  The hardest to implement is division.  The hardest type of division to implement is when the divisor is larger than the capacity of the CPU registers.  Knuth gives a method of calculatiing the trial divisor in this case, but it is not completely definitive, and has to be checked by multiplying the quotent by the trial divisor.  It is a long and tedious algo.  A lot of "high precision" arithmetic packages don't have this large divisor capability, and that is why.  There is a lot of material about this subject is in number theory references, and this ground has been plowed many times.  You owe it to yourself to read the literature before you attempt to code, so you don't reinvent the wheel.  Some folks claim to be able to do big division without using Knuth's method, but I don't know how they do it or if it is a better method.  Ratch