numbers of arbitary size (BigNum) - Programmers Heaven

#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

# numbers of arbitary size (BigNum)

Posts: 29Member
Hi coders,

I want to calculate big prime numbers. To test if a number is prime i want to use the Mille-Rabin-Algo, but the calculation of "2^x" (for x > 1023) isn't possible with datatypes like "double". The result is simply to big. For example my C# calc says that "(2^1024) - (2^1024 + 1)" isn't 1. To calculate numbers of arbitary size i can't use the standardized datatypes of C# .NET.

The GNU MP is a package to handle with numbers of arbitary size. But it is programmed for C and GNU compilers.

My question is: Is there a useful package for C# .NET to calc numbers of arbitary size?

Though they know that bignums are essential for scientific calcs, MS wasn't so friendly to bring a bignum datatype with the .NET Framework.

• Posts: 1,784Member
• Posts: 29Member
:

huh?
• Posts: 1,784Member
: Hi coders,
:
: I want to calculate big prime numbers. To test if a number is prime i want to use the Mille-Rabin-Algo, but the calculation of "2^x" (for x > 1023) isn't possible with datatypes like "double". The result is simply to big. For example my C# calc says that "(2^1024) - (2^1024 + 1)" isn't 1. To calculate numbers of arbitary size i can't use the standardized datatypes of C# .NET.
:
: The GNU MP is a package to handle with numbers of arbitary size. But it is programmed for C and GNU compilers.
:
: My question is: Is there a useful package for C# .NET to calc numbers of arbitary size?
:
: Though they know that bignums are essential for scientific calcs, MS wasn't so friendly to bring a bignum datatype with the .NET Framework.
:

My answear to your Q was to use the decimal type. It's floating point, but it doesn't matter...
It holds 20 digits or so I think. It's made to hold really big numbers, wich you want.

One reason for there isn't such a package in .net is that it isn't possible to program good in .net . In all other languages it's easy, just use a pointer and add with carry.

In asm it'll look like this:
[code]
;program to add 2 64 bit numbers at bx,dx and store at di
mov ax,0
mov cx,0
add ax,cx ;clear carry flag... (I can't remember the instruction for this...)

rept 4 counter{
mov ah,[bx+4-counter]
mov ch,[dx+4-counter]
mov [di+4-counter],ah
}
[/code]
The number 4 is the number of bytes the data is. It's possible to add 128bit numbers like this.

[grey]The one and only [b]Niklas Ulvinge[/b][/grey] [white]aka [b]IDK[/b][/white]

• Posts: 29Member
: My answear to your Q was to use the decimal type. It's floating point, : but it doesn't matter...
: It holds 20 digits or so I think. It's made to hold really big : numbers, wich you want.

"decimal" is even smaller than "double". And it is not my aim to hold really big numbers, i talk about 2^10000 and much more.

type maximum
ulong 1.84*(10^19)
decimal 7.9*(10^28)
float 3.4*(10^38)
double 1.7*(10^308) !!
??? endless

: One reason for there isn't such a package in .net is that it isn't : possible to program good in .net . In all other languages it's easy, : just use a pointer and add with carry.

huh? I think .NET is the easiest SDK since Borlands VCL.

A pointer could hold everything, but i need to handle this numbers. I want to use predefined addition, multiplication, division, modulation and the ^-thing(don't know the english word).

thx for response.

Bert.

PS: nice homepage
• Posts: 1,784Member
[b][red]This message was edited by IDK at 2005-11-26 9:37:14[/red][/b][hr]
: : My answear to your Q was to use the decimal type. It's floating point, : but it doesn't matter...
: : It holds 20 digits or so I think. It's made to hold really big : numbers, wich you want.
:
: "decimal" is even smaller than "double". And it is not my aim to hold really big numbers, i talk about 2^10000 and much more.
:
: type maximum
: ulong 1.84*(10^19)
: decimal 7.9*(10^28)
: float 3.4*(10^38)
: double 1.7*(10^308) !!
: ??? endless
:
: : One reason for there isn't such a package in .net is that it isn't : possible to program good in .net . In all other languages it's easy, : just use a pointer and add with carry.
:
: huh? I think .NET is the easiest SDK since Borlands VCL.

[blue]Yes, but it doesn't got add with carry, and you can't asm in it... (I'll maybe learn msil, and do something like this in it)[/blue]

: A pointer could hold everything, but i need to handle this numbers.

[blue]Look at my asm code. It's OK if you don't understand it, but the thing with it is that it can add BIG numbers like 256 bit. It requieres pointers and add with carry though.[/blue]

:I want to use predefined addition, multiplication, division, modulation :and the ^-thing(don't know the english word).

[blue]^ is called raised to in english. In C/C++ this ^ symbols the xor operation, wich is compleatly different. I'm swedish, and didn't know what it was named before eather.[/blue]

: thx for response.
:
: Bert.
:
: PS: nice homepage
:
My webhost is down, so I can't do anything with it :-(
• Posts: 1,784Member
: : type maximum
: : ulong 1.84*(10^19)
: : decimal 7.9*(10^28)
: : float 3.4*(10^38)
: : double 1.7*(10^308) !!
: : ??? endless
: :
ulong = 2^64
double * (2^ulong)
1.7*(10^308) * (2^(2^64))

I think that's big enough....
So now I'm doing a struct that will do this.

Do you want me to send you the code when I'm done?
• Posts: 29Member
: ulong = 2^64
: double * (2^ulong)
: 1.7*(10^308) * (2^(2^64))
:
: I think that's big enough....
: So now I'm doing a struct that will do this.

this would be about 1.7*(10^327). This isn't big enough and i think you don't understand. I need numbers of arbitary size(there is no "big enough") and special operators which handle these numbers. My calculation is "a^(n-1) mod n; (n,a element of naturals & unknown size)". n is maybe "(2^25964951)-1", this is a number with 7816230 decimals. A datatype with a size of (10^7816230)!
• Posts: 1,784Member
: : ulong = 2^64
: : double * (2^ulong)
: : 1.7*(10^308) * (2^(2^64))
: :
: : I think that's big enough....
: : So now I'm doing a struct that will do this.
:
: this would be about 1.7*(10^327). This isn't big enough and i think you don't understand.

If I first make a small type then it would be easy to make it bigger.

: I need numbers of arbitary size(there is no "big enough") and special
: operators which handle these numbers. My calculation is "a^(n-1) mod n;

Why didn't you say so. This is easy to cheat.
If you'll think a little it's easy to do this.
What you want is x^y mod z to simplify.
You really don't want to have that big x^y but only the small value of
x^y mod z.

Hardcode some math and it will work with int.
There's lots of people who do it like you.
One of them invented a really interesting fast power formula...
• Posts: 29Member
I found it in a Newsgroup.