A C++ Question

[Deiphos]

I don't know if there are any programmers here, but I will try my luck

I want to handle an extremely huge number in C++, in the order of more than 1000 digits. I know this is huge, but I am sure it can be done, but I don't know how

Do you guys know of any way I can do this? I have tried something else aswell, I converted the number into BCD (binary-coded digit) format, and I was wondering if there might be a way to convert that into pure binary form if the 1000+ digit thing doesn't work.

Thanks

 

[|tera|]

Ask prometheus, maybe he knows

 

[Highflyer_GP]

Tried making it of type long?

 

[Moederloos]

depends on what you want to do (as always )

Anyways, to add two numbers together, and they can be any length your computer has space to store, shove it into memory as a "string". Now, add the LSD of each number, store the result, flag a carry if needed and move to the next two LSDs. and so on.

Inelegant - yes. Does it work? yes again

Each problem will have a solution, just need to define the problem.

If you give me some details, I will try a PHP app when I get bored

 

[Deiphos]

well, what I basically want to do is convert a number of 1400 digits into pure binary. The way of doing this is to mod by 2, and then div by 2 until the number you are divving is 0. Now no var type in C++ will support that kind of operation, a unsigned long isn't even large enough.
I can't use a float, because it obviously has to be a precise thing.

 

[ant1b0dy]

well, what I basically want to do is convert a number of 1400 digits into pure binary. The way of doing this is to mod by 2, and then div by 2 until the number you are divving is 0. Now no var type in C++ will support that kind of operation, a unsigned long isn't even large enough.
I can't use a float, because it obviously has to be a precise thing.

You'll have to write your own division function that works with string representations of the numbers. I've written code to add and multiply arbitrary length numbers for some bank hashing algorithms previously, but I haven't had to do division yet.

Just write an algorithm that divides by 2 using the long division method you learned at school.

May I ask why you need to do this?

 

[Deiphos]

Well, PHP doesn't like huge numbers either, try running this little script, and you will see what I mean:

<?php

    $number = 65465484132151654987413135164164987974841321032116548798713156;
    $bin = array();

    do {
        $bin[]  = ($number % 2);
        $number = $number / 2;
    } while (round($number) > 0);

    $bin = array_reverse($bin);

    for ($a = 1; $a < count($bin); $a++) {
        echo $bin[$a];
    }

?>

May I ask why you need to do this?

Well, it is in a study of primes, especially things where programs are encoded into prime numbers, then by converting that prime number into binary, it will be the gziped source code of a program. The number I am trying to do is this one here: http://en.wikipedia.org/wiki/Illegal_prime

I am trying to write a program that will take any program, change its binary data into a number, then that number will be like an encoded version of the code, it is just something that sparked my interest.

A perl script has been written to do this, but I don't know much perl, and the methods used in that script are unknown to me

 

[dabean]

If by 'pure binary' you mean you want it in '10110' format, that's string to string (assuming you read the value in as a string).

 

[Deiphos]

The method I use to get a number into binary is shown in that PHP script I wrote, it is the exact same method used in C++. The number is read in through a file, so esentially it is a string, but to convert it to binary you have to do some sort of mathematical operation on it, which can't be done on a string.

 

[Myrrdin]

If you don't mind taking a dependency on the J# libraries, you already have a big number implementation at your disposal. In fact, you have two.

The J# run-time library, vjslib.dll, is available as a redistributable component, just like the .NET Framework. You can download it from Visual J# Downloads (it's also installed as a prerequisite by Visual Studio®). In the same manner that a C# or C++ application can make use of Microsoft.VisualBasic.dll (the Visual Basic run-time library), C#, Visual Basic®, and C++ applications can use the J# run-time library and the numerous interesting classes it exposes.

Some folks use the J# Zip libraries to meet their compression requirements (see Zip Your Data: Using the Zip Classes in the J# Class Libraries to Compress Files and Data with C#), but beyond that there are some very interesting gems hidden in the library. For your needs, I suggest you see the java.math.BigInteger class (a BigDecimal class is also available). Here's an example of using BigInteger, showing that it can be used with values larger than the largest UInt64:

BigInteger i = new BigInteger(ulong.MaxValue.ToString());
BigInteger iSquared = i.multiply(i);
Console.WriteLine("i:\t" + i);
Console.WriteLine("i^2:\t" + iSquared);


This outputs:

i: 18446744073709551615
i^2: 340282366920938463426481119284349108225


BigInteger exposes a large number of operations. This includes the standard operations, such as addition, subtraction, multiplication, division, and modulation, but it also exposes functionality such as the ability to find the GCD of two BigIntegers, primality testing, bit set testing, and conversion to other data types. All in all, it's a very useful class.

Of course, an answer on this subject wouldn't be complete without a strict warning. Most of the time I hear people asking for such primitives, it's because they want to roll their own cryptographic operations. Don't do it. You'll quite likely be opening yourself up to a world of hurt. Instead, use the classes in the System.Security.Cryptography namespace. If they don't meet your needs (which they should most of the time), consider using the unmanaged Crypto API. If that doesn't meet your needs, look into implementations from trusted vendors. Don't roll your own.

While you're considering exploring vjslib.dll, look around a bit. There are a lot of interesting classes available there that might help you in your projects.

Googled this for ya. Source http://msdn.microsoft.com/msdnmag/issues/05/12/NETMatters/

Google is your friend.

 

[Moederloos]

Google is your friend.

My brilliant programming skills rely more on Google than any inherent ability.

 

[Deiphos]

Thanks Myrrdin, but would it support a number like the one I linked to in my previous post, it doesn't seem to at first glance.
I think I will do what ant1d0dy said, which is to do long division on the number

 

[Myrrdin]

Deiphos

I think 2 to the power of 64 – 1 digits should be enough.

There’s no theoretical limit to how big the numbers can be using these classes. They use it to do cryptography calculations. And that gets pretty big. Plus its an array of digits so your conversion to binary could be done via the array.

and property isProbablePrime for your prime calculation.
Returns true if this BigInteger is probably prime, false if it's definitely composite.

See http://java.sun.com/j2se/1.4.2/docs/api/java/math/BigInteger.html for more info.

LOL @ Moederloos.

 

[Deiphos]

Oops, it is early in the morning and I haven't fully woken up yet
Thanks