Print really big numbers

Question

Hey!

I have this code

#include <iostream>

using namespace std;

int main(int argc,char **argv) {

    unsigned long long num1 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995LL;
    unsigned long long num2 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999996LL;
    unsigned long long num3 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997LL;
    unsigned long long num4 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998LL;
    unsigned long long num5 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999LL;

    cout << (unsigned long long)(num1 * num2 * num3 * num4 * num5) << endl;
    return 0;
}

As you can see the numbers are enormous, but when I do the math there I get this: 18446744073709551496

Also at compile time I get lot's of warnings:

warning: integer constant is too large for its type| In function `int main(int, char**)':| warning: this decimal constant is unsigned only in ISO C90| ...

Any help will be appreciated :D

Answer 1

unsigned int represents a system word. Today, that word will max out at either 2^32 -1 or 2^64 - 1, depending on whether your system is 32 bit or 64 bit. You're hitting the cap.

You have to write a bignum class or use one off the 'net.

Why are you doing this problem anyway?

Answer 2

Those numbers won't fit into any C++ data types. If you just want to print them, store the numbers in a string. If you want to do math on it, find an arbitrary precision math library and use that.

Answer 3

Your result is larger than the long long type - you need to look at a BigInteger or arbitrary precision library, something like gmp

Answer 4

The answer that you got, 18446744073709551496, is due to your 999...9s being truncated when assigned to a long long, plus the multiple operations overflowing. Its deterministic, but effectively just a random collection of bits.

Answer 5

If you want literals this big in your code, you'll have to enter them as string literals and load them into a BigInt class of some sort. There's no way to express integer literals that big in source code right now (although C++0x will hopefully address that shortfall).

If you're using the BigInteger library, take a look at the stringToBigUnsigned function in BigIntegerUtils.hh for building a big integer from a string.

#include "BigUnsigned.hh"
#include "BigIntegerUtils.hh"     

 BigUnsigned  num1 = stringToBigUnsigned (
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999999999999999999999999999999999999999999999999"
    "99999999999999999999999999999999999995"
    );

Answer 6

Hey!

I am now using the BigInteger library but I am still getting errors :(

If I do

BigUnsigned  num1 = 1234;

It works, but if I do:

BigUnsigned  num1 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995;

I get this:

||=== Problem8, Debug ===| D:\programacao\progsmeus\c++_progs\projecteuler.net\problem8\main.cpp|19|warning: integer constant is too large for its type|

D:\programacao\progsmeus\c++_progs\projecteuler.net\problem8\main.cpp||In function `int main()':|

D:\programacao\progsmeus\c++_progs\projecteuler.net\problem8\main.cpp|19|warning: this decimal constant is unsigned only in ISO C90|

D:\programacao\progsmeus\c++_progs\projecteuler.net\problem8\main.cpp|19|error: integer constant is too large for "long" type|

D:\programacao\progsmeus\c++_progs\projecteuler.net\problem8\main.cpp|19|error: conversion from long long unsigned int' to BigUnsigned' is ambiguous|

D:\programacao\progsmeus\c++_progs\projecteuler.net\problem8\BigIntegerLib\BigUnsigned.hh|62|note: candidates are: BigUnsigned::BigUnsigned(short int)|

D:\programacao\progsmeus\c++_progs\projecteuler.net\problem8\BigIntegerLib\BigUnsigned.hh|61|note: BigUnsigned::BigUnsigned(short unsigned int)|

D:\programacao\progsmeus\c++_progs\projecteuler.net\problem8\BigIntegerLib\BigUnsigned.hh|60|note: BigUnsigned::BigUnsigned(int)|

D:\programacao\progsmeus\c++_progs\projecteuler.net\problem8\BigIntegerLib\BigUnsigned.hh|59|note: BigUnsigned::BigUnsigned(unsigned int)|

D:\programacao\progsmeus\c++_progs\projecteuler.net\problem8\BigIntegerLib\BigUnsigned.hh|58|note: BigUnsigned::BigUnsigned(long int)|

D:\programacao\progsmeus\c++_progs\projecteuler.net\problem8\BigIntegerLib\BigUnsigned.hh|57|note: BigUnsigned::BigUnsigned(long unsigned int)| ||=== Build finished: 2 errors, 2 warnings ===|

I have read in the BigUnsigned that it is suppose to hold a number as big as big as my ram, but... this big number wouldn't occupy 2gb of ram

Help me out please

Answer 7

What is it you are trying to do? Do you understand the basics of binary and decimal numbers? Why 8 bits only holds the values 0 to 255, 12 bits 0 - 4095, etc? How many bits does it take to hold the number you are interested in? Or better, how big of a number are you interested in creating? And are you using 9s to make the number bigger? What about hex 0xF... instead? If you want the biggest unsigned number (within one of the standard integer types) why not:

unsigned long long a,b;

a = -1; //which just seems wrong mixing signed and unsigned but it is valid, the number is converted to unsigned before storing

b = 0; b--; //does the same thing as above

Do you really need precision at that level? You realize that multiplies can require a result twice the size of each operand? 0xFF * 0xFF = 0xFE01, if in this case you were using 8 bit integers you could not do the math. It only gets worse as you continue to multiply 0xFF * 0xFF * 0xFF = 0xFD02FF.

What are trying to do?

---

Seeing your response:

I have not seen euler number 8 before. Sounds like a good interview question as it only takes a few lines of code to solve.

---

Your other response:

Numbers...

Likely because we have 10 fingers (and perhaps 10 toes) we grow up with "base 10". Our clocks are base 60 for the most part but it has been mixed with base 10 to make it more confusing. Anyway, base 10, means for each number placeholder you have one of 10 unique digits, when you reach the maximum in that place you roll over to the next place. This is all elementary school stuff.

000
001
002
003
...
008
009
010
011
012
...

See how the right most digit has 10 symbols (0,1,2,3,4,5,6,7,8,9) and when it reaches the last symbol it starts over and the one to the left of it increments by one. This rule is true for all base numbering systems.

It is true for base 2 except there are only two symbols, 0 and 1

000
001
010
011
100
101
...

Same is true for octal, but 8 symbols (0,1,2,3,4,5,6,7)

000
001
002
003
004
005
006
007
010
011
012
013
...

And the same is true for hexadecimal, 16 symbols(0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f)

000
001
002
003
004
005
006
007
008
009
00a
00b
00c
00d
00e
00f
010
011
012
013
...

I was about to go into the whys of using binary over other bases (like 10) in computers. The bottom line it is easy to have two states on or off, or high and low. Two states is like two symbols 1 and 0 in base 2. Trying to keep electronics tuned to more than two states within the available voltage is tough, at least it used to be, keeping it near zero volts or above some small number of volts is relatively easy, so digital electronics use two states, binary.

Even a simple task for a human in binary is long winded, simple second grade math is still a lot of ones and zeros. So octal became popular because it allowed you to think in groups of three bits and you could use symbols we are familiar with as numbers 0,1,2,3,4,5,6,7. But groups of four which is another power of 2, gives the humans a lot more mental computing power than octal, hex is based on 4 bits which is also a power of 2. We had to add more symbols to the 10 we borrowed from the traditial arabic base 10, so the first 6 of the alphabet was used. Octal is rarely if ever used, you can tell someones age if they think octal instead of hex. (I am from the hex generation but have worked with those from the octal generation that struggle with hex because they cannot get from octal to binary to hex in their mind).

Base 10 in a computer is like the average human thinking in hex. computers dont do base 10 (well for lazy humans they used to do bcd), they do base 2. The decimal number 1234 in a computer is really 0x4D2 or 0b010011010010. That is as a value, say you want to add 1234 plus some other number you need that value which has nothing to do with the symbos 1, 2, 3, and 4. But to post this answer on stackoverflow we dont use the number we use ASCII, so 1234 in ascii is 0x31, 0x32, 0x33, 0x34, which is important to know for your euler solution assuming the 1000 digit number was provided as an ascii string, which it would have to be or you would have to convert it from binary to ascii since the problem is a base 10 problem and not base 2 by definition.

So back to what I had asked. Say you had 4 bits of memory to store a number, how big of a number could you store? If you think base 10 only you might think that number is a 9, because you are trained to think of using the biggest symbol in each storage location, 99999 is the biggest number if you have 5 storage locations in base 10. Back to four bits though, the biggest symbol for a single bit is 1, put that number in each storage location you get 1111 (four ones). Just by looking at those four ones you should be able to in your mind easily see the octal and hex version of that same number 17 octal or F hex. To see decimal takes math, or in this case memorization, that number is 15 decimal. So the biggest four bit number you can have is 0xF or 15 not 9. What about an 8 bit number? 0xFF or 255 (2 to the 8th power minus one). Biggest 16 bit number? 65535, etc.

So when I ask how many bits are you trying to use this is what I mean. Look at this number 99999. Again base 10 you would think that is the biggest number, but to a computer it is only part way there, 99999 decimal is 0x1869F, which takes 17 bits of memory to store, the biggest 17 bit number you can store is 0x1FFFF which is 131071 which is a bit bigger than 99999. So when you want to think big numbers and math on a computer you have to think binary (or hex).

Originally you were doing multiplications, which is still part of the euler problem, but what was I was asking about was related to precision and bit storage. Here are some fundamentals, and I wont get into it but you can see why we rely on floating point units in computers.

Take the largest 4 bit number 1111(binary), which is 15 decimal. Add that with the largest four bit number and you get 15+15 = 30 = 0x1E or 11110 binary. So to add two four bit numbers you need five bits to hold your answer. Computers keep a "carry" bit for this extra bit. Essentially the add/subtract integer math functions in the computer allow you to have N+1 bits. So if it is an 32 bit computer you basically have 33 bits for add/sub math.

The problem is multiply and divide, which even today many processors do not support (yes many have no fpu and only do add and subtract, sometimes multiply, but divide is rare. Multiply and divide take a lot of electronics the trade off is you can do them with adds and subtracts in software). Take the worst case multiply for a four bit system 1111 * 1111 = 11100001 so it takes 8 bits to store the result of a 4 bit multiply, you will quickly find that if you had a 4 bit system MOST of the multiplies you want to do will result a number that cannot be stored in 4 bits. So when I saw you taking 64 bit integers (the unsigned long long is often 64 bits) and multiplying four times, that means you need 64*5 or a 320 bit integer to store your answer, you were trying to put that answer in a 64 big result, which quite often, depending on the compiler and computer will happily do and will truncate the upper bits leaving you with the lower 64 bits of the result which can easily look smaller than any of your operands, which is what I had thought you might have done at first.

Floating point is not much more than scientific notation but in binary, if you wanted to multiply the number 1234 and 5678 using scientific notation you would take 1.234*10^3 times 5.678*10^3 and get 7.007*10^6. You keep your precision and are able to represent a wider range of numbers. I wont get into how this works in binary. But it doesnt work for your original question.

Ahh, the last thing to clarify what I was doing in my question/response. Negative integers in binary. Because of the relationships between addition and subtraction and base systems you can play some tricks. Say I wanted to subtract 1 from the number 7(decimal) using binary. Well there is no such thing as a subtract circuit, you instead add a negative number so instead of 7 - 1 it is really 7 + (-1), it makes a difference:

0111 + ???? = 0110

What number could you add to 7 to get 6...in binary?

0111 + 1111 = 0110

Negative numbers in binary are called "twos complement", long story short the answer is "invert and add 1". How do you represent minus 1 in binary? take plus one 0001 then invert it meaning make the ones zeros and the zeros ones (also known as ones complement) 1110 then add one 1111. Minus one is a special number in computers (well everywhere) as no matter how many bits you have it is represented as all ones. So when you see someone do this:

unsigned char a;

a = -1;

The compiler first looks at that -1 and thinks ...11111(binary) then it looks at the equals sign and the other side, oh, you want a to be all ones, it sees that you have a signed integer and an unsigned but the conversion is to just move the bits over so you are saying above that you want a = 0xFF; (assuming an 8 bit unsigned char).

Some compilers may complain that you are trying to store a negative number in an unsigned number. Other compilers will look at that -1 and see it as a 32 bit or these days maybe 64 bit signed integer constant and then when it evaluates the equals into an 8 bit unsigned you will get a warning that you cannot store -1 in a signed or unsigned char without a typecast. But if you do this:

a = 0; a--;

All compilers will like that. and wont complain, it just burns computing cycles at runtime instead of compile time.

Now somewhere a friend told me of a book that does binary math serially. For example to negate a number, usually you do the invert and ad one trick, but with pencil and paper some may tell you the other trick. Starting from the right copy the zeros up to and including the first 1 then invert after that, so minus 2

0010
1110

Starting from the right copy the 0 then the first one, then invert the remaining bits as you go left.

minus 6

0110
1010

minus 4

0100
1100

Supposedly there are tricks to do add and subtract (well duh, those are easy) but also multiply and divide. If you do them serially then you can do infinitely long math in binary with the same alu. If you were to know how to do that you could implement that in software and your original question of multiplying big constants (with the assumption of retaining all the precision) is trivial on any computer.

Answer 8

I never really understood hex numbers. I am not to used to programming in C++ just PHP. I am trying to do the Euler problem number 8 which asks for the product of 5 consecutive 1000 digit numbers.

Could you tell me where I can get some good information on what you were talking about in your post about hex numbers? There is a lot of stuff in google but maybe you can tell me a good tutorial or something!

Thanks

Answer 9

Ok ok I didn't understand the problem!

It's not the result of 5 1000 digit numbers it's 5 consecutive digits in the given 1000 digit number :P

Guess my English isn't that great :(