very big number help

I just learned to program C++ about 5 weeks ago and I’ve run into a few problems…

I’m writing a piece of software that will capture n-dimensional events (points) using a specialized type of n-complex. I need to generate the normal for some of the n-simplices which make up the complex (in 3d terms, simplex = triangle, complex = figure). My problem is integer overload error where I’m multiplying a number, 0 <= P <= 409600 up to 15 times. Does anyone know a routine to handle very big numbers like this?

The use is in finding a determinant. I was told about pictesting, but from what I heard it fails to handle cases with dimensionality outside of 3.

Gee, , that would seem to need 280 bits of precision (if done by brute force). I’ve only seen supercomputer applications that used that level of precision.

I know it’s no help, but mathematical programs deel with big numbers without any trouble. (Maple being one)
It can handle almost any size numbers being multiplied (ie 10 to the power of 600) etc. if you have the time to wait. (not too long in your case)
I no longer have the program, but I imagine it can handle cases as large as anyone would want.
I know this doesn’t solve your problem, but solutions do exist. (I’m pretty sure anyway- there’s a slight chance I have no idea what I’m talking about)

For maths librarys you can try these sites:

NTL http://www.shoup.net/ntl/

and theres a crypto site here with links to a couple of librarys which deal with large numbers:
http://ruby.und.nodak.edu/org/crypto/crypto/resources.html

Hopefully my passing interest in factoring primes will prove useful to sombody

Kilby…

Sorry to change the topic but…

Kilby what is factoring primes?
(caught my attention sounds like for fun math stuff (gee now i sound like a geek))

Is that like
hhmmmm…
whats the name again…
is it Menson Prime Number’s…
nope not that but something that sounds like it

or is it like…
trying to prove that any even number is the sum of 2 primes (thata sort thing)

Chris

[This message has been edited by Whittick (edited 07-28-2000).]

Factoring numbers created by multiplying two primes?

Try not to use integer variables but floating point variables. You will lose accuracy but this should not overload.

The problem is that I have to keep signigicant accuracy. So far my solution is this (I have to do a dot product of the determinant and various vectors and I have to be super accurate … it’s the whole point of the program: we already have one which isnt accurate):

let CBigAssNum be a class with 2 member variables:

unsigned int* banui = new int[10];
bool sign = false;

Since it’s in C++ I can define my own multiplication and addition by considering the integers as binary strings and using various combinations of AND and bitwise shifting. Unfortunately I’ve never overloaded a operator before and I’m not currently having any success.

This class will be inherited by by CtEvaluator which uses CBigAssNum to determine if the t paremetrization value of the ray from the point (down the x axis) is greater than or equal to zero (I’m drawing a ray from an point and if it strikes an n-simplex it gets a thumbs-up, an odd number of strikes = inside, even = outside).

You could try using long doubles, that would give you 80bit of precision, though for large numbers like you’re asking, it won’t give you that last digit.

I’ve created Math libs like this in assembly for old motorola processors. If you know intel assembly it would be pretty straight forward. But I’m guessing you don’t or you would have done this. From what I’ve seen and heard of intel assembly it is pretty nasty stuff.

A slow way to hack around this would be to make a class holding a bunch of long ints. Inside this class when the first long int overflows add one to the second long int. When the second long int overflows add one to the third long int and so on. In essence you’d just be stringing a bunch of long ints together.

I’m not sure how much a compiler will optimize this but it would be really fast if it optimizes propertly, but it probably won’t. It will work though. Oh and don’t forget when multiplying you may have multiple overflows.

http://www.geocities.com/CapeCanaveral/Hangar/8802

Ok, if you have created your class and want to define your own multiplication and addition, try this :

CBigAssNum CBigAssNum: perator*(CBigAssNum &Term)
{
// define this * Term here
}

CBigAssNum CBigAssNum: perator+(CBigAssNum &Term)
{
// define this + Term here
}

is : followed by o (I should have checked disable smilies )

I have read something about so called ‘string arithmetic’ years ago. That is you have two strings (char AnyName1[AnyNumber],AnyName2[AnyNumber]) where you store decimal numbers in ASCII. You have to write your own mathematical functions but thats rather easy. They do exacly that what you do if you calculate something on a sheet of paper. OK it’s surely quite slow and not very memory efficient, but you can push up accuracy simply by increasing the string size where you are only limited by memory. Hope it helps a little bit.

This is a part of a HugeInt.h file I wrote some time ago which might help you along the way …

#pragma warning(disable: 4035)

void Add(unsigned char *var, unsigned int len, unsigned char ToAdd){
_asm {
MOV EDI, var
MOV ECX, len
MOV AL, ToAdd
DEC ECX
ADD [EDI], AL
Addit:
INC EDI
ADC BYTE PTR [EDI], 0
DEC ECX
JNZ Addit
}
}

void Sub(unsigned char *var, unsigned int len, unsigned char ToSub){
_asm {
MOV EDI, var
MOV ECX, len
MOV AL, ToSub
DEC ECX
SUB [EDI], AL
Subit:
INC EDI
SBB BYTE PTR [EDI], 0
DEC ECX
JNZ Subit
}
}

void Mul(unsigned char *var, unsigned int len, unsigned char ToMult){
_asm {
MOV EDI, var
MOV ECX, len
MOV BL, ToMult
XOR BH, BH
Multit:
MOV AL, [EDI]
MUL BL
ADD AL, BH
MOV BH, AH
MOV [EDI], AL
INC EDI
DEC ECX
JNZ Multit
}
}

unsigned char Div(unsigned char *var, unsigned int len, unsigned char ToDiv){
_asm {
MOV EDI, var
MOV BL, ToDiv
ADD EDI, len
XOR AX, AX
DEC EDI
Divit:
MOV AL, [EDI]
DIV BL
MOV [EDI], AL
DEC EDI
CMP EDI, var
JAE Divit
MOV AL, AH
}
}

Just to make sure the way this is set up:

The functions are for integer character (like on paper), so that a full add would consist of a series of Add’s and Sub’s, just like on paper (i.e. add the right most numbers, put the Sub 10 value into the final char of the output, carry the Div 10 (0 or 1), then add all three numbers for the next line etc. etc.)

That way I can use the happy-fast assembler for the pieces of the functions?

Could someone could tell me if the solution I came up with is not optimal?

I have a “string” of integers.
Adding consists of two parts: a partial adder and a full adder. The partial adder correctly adds any one int to the string of ints, allowing you to specify how far along the string it adds. The full adder simply takes two strings and chops the second string into integers passing the first string and the pieces of the second string to the partial adder:
example: assume 10 = 0;
fa: 0 0 3 5 9 + 0 0 1 2 9 =
pa: 0 0 3 5 9 + 0 0 0 0 9 = 0 0 3 6 8
pa: 0 0 3 6 8 + 0 0 0 2 0 = 0 0 3 8 8
pa: 0 0 3 8 8 + 0 0 1 0 0 = 0 0 4 8 8
//non-similar signed bigint adds are sent to
//subtracts and vice versa
subtractor simply subtracts each of the Y values from 9, then adds 0 0 … 0 1 to Y
fs: 0 0 3 5 9 + 0 0 1 2 9 =
fs: 0 0 3 5 9 + 0 0 8 7 0 =
fs: 0 0 3 5 9 + 0 0 8 7 1 =
fa: 0 0 3 5 9 + 0 0 8 7 1 =
pa: 0 0 3 5 9 + 0 0 0 0 1 = 0 0 3 6 0
pa: 0 0 3 6 0 + 0 0 0 7 0 = 0 0 4 3 0
pa: 0 0 4 3 0 + 0 0 8 0 0 = 0 0 2 3 0
multiply copies the X to lsft and Y to rsft and creates a string called holder: there is a defined right-shifter and defined left shifter: if rsft is odd then I add lsft to the holder, if not, then nothing; it does this strlen*wordlen, doing a left shift to lsft and a right shift to rsft after each addition to the holder.

I’m thinking of adding a checker to see if the rsft == 0, that way it can abort the multiply at that point. This has it’s ups and downs: if rsft is “long” then the time to multiply is short, but if less than 1/2 of rsft is used, then I see savings. I want to do this, because in most cases I will be multiplying a single integer string by a 20 integer string which would shave off 18 units of time?

The functions are for integer character (like on paper), so that a full add would consist of a series of Add’s and Sub’s, just like on paper (i.e. add the right most numbers, put the Sub 10 value into the final char of the output, carry the Div 10 (0 or 1), then add all three numbers for the next line etc. etc.)

No, the HugeInts are binary so you can add any number from 0…255 to the HugeInt.
It wouldn’t be hard to extend the add and sub functions to add two HugeInt together either … but Mul/Div would require some hard work …

[This message has been edited by Humus (edited 08-01-2000).]

In fact if you only need to multiply with number < 409600 then you do not have to implement multiplication.

Here is a small algo that could help you :

First you need a shift fonction that will shift your number to the left

shift (123456789) = 1234567890

That should be quite easy to code.

Then you can do this (recursive def)

Very_long_int Mult(long int X,very_long_int Y)

{
Ytemp = Y

result = {
for i = 1 to (X modulo 10)
Ytemp= add(Ytemp,Y)
next
}

Y=Ytemp

Mult(X,Y) = ad(shift(Mult (X/10,Y)) , result)
}

This is algorithmic not code so feel free to adapt.

I choosed base 10 because you are using table of char, if you change for something else keep the base acurate (make the shift part easy):
for binary use base 2
for hexa use base 16

Exemple 1284 x 8 = (1280 + 4) x 8
= shift(128x8) + 4x8

Hope this can help

Kha

[This message has been edited by kha (edited 08-04-2000).]