Howdy, Stranger!

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

Sign In with Facebook Sign In with Google Sign In with OpenID

Categories

We have migrated to a new platform! Please note that you will need to reset your password to log in (your credentials are still in-tact though). Please contact lee@programmersheaven.com if you have questions.
Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

numbers of arbitary size (BigNum)

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.

Comments

  • IDKIDK Posts: 1,784Member
  • IDKIDK 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.
    :
    Sorry, this site had some problems before... But now it works. I forget about this one...

    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]
    adc ah,ch
    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]

  • VanilleBertVanilleBert 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
  • IDKIDK 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 :-(
  • IDKIDK 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?
  • VanilleBertVanilleBert 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)!
  • IDKIDK 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...
  • VanilleBertVanilleBert Posts: 29Member
    I found it in a Newsgroup.

    [1] Download & Install "Visual J# .Net Redistributable Package"
    In IDE: Add Reference "vjslib"
    In Code:
    [code]
    using java.math;
    BigInteger n = new BigInteger("123456789");
    BigDecimal d = new BigDecimal("123456789.987654321");
    [/code]

    [1] http://www.microsoft.com/downloads/details.aspx?displaylang=en&FamilyID=301f28aa-49b6-4b32-832c-873707e50834
Sign In or Register to comment.