Huge number in delphi

Question

I'm writing a program and I multiply numbers by 5... For example:

var
  i:integer;
  k:int64;
begin
  k:=1;
  for i:=1 to 200000000 do
  begin
    k:=5*(k+2);
  end;
  end;
end.

But when I compıle and start my program I get an overflow integer error. How can I solve this problem?

Answer 1

The correct value of k will be at least 5^20,000,000, or 2^48,000,000. No integer type on a computer is going to be able to store that; that's 48,000,000 bits, for crying out loud. Even if you were to store it in binary, it would take 6,000,000 bytes - 5.7 MB - to store it. Your only hope is arbitary-precision libraries, and good luck with that.

What are you trying to compute? What you are doing right now is computing a sequence of numbers (k) where the ith element is at least as big as 5^i. This won't work up to i = 20,000,000, unless you use other types of variables...

Answer 2

@Patrick87 is right; no integer type on a computer can hold such a number.
@AlexanderMP is also right; you would have to wait for a very long time for this to finish.

Ignoring all that, I think you’re asking for a way to handle extremely large number that won’t fit in an integer variable.
I had a similar problem years ago and here's how I handled it...

Go back to the basics and calculate the answer the same way you would if you were doing it with pencil and paper. Use string variables to hold the text representation of your numbers and create functions that will add & multiply those strings. You already know the algorithms, you learned it as a kid.

If your have two functions are MultiplyNumStrings(Str1, Str2) & AddNumStrings(Str1, Str2) you sample code would look similar except that K is now a string and not an int64:

var
  i : integer;
  k : string;
begin
  k := '1';
  for i:=1 to 200000000 do
  begin
    k := MultiplyNumStrings('5', AddNumStrings(k, '2'));
  end;
end;

This function will add two numbers that are represented by their string digits:

function AddNumStrings (Str1, Str2 : string): string;
var
  i : integer;
  carryStr : string;
  worker : integer;
  workerStr : string;
begin
  Result := inttostr (length(Str1));
  Result := '';
  carryStr := '0';

  // make numbers the same length
  while length(Str1) < length(Str2) do
    Str1 := '0' + Str1;

  while length(Str1) > length(Str2) do
    Str2 := '0' + Str2;

  i := 0;
  while i < length(Str1) do
  begin
    worker := strtoint(copy(Str1, length(str1)-i, 1)) +
              strtoint(copy(Str2, length(str2)-i, 1)) +
              strtoint (carryStr);
    if worker > 9 then
    begin
      workerStr := inttostr(worker);
      carryStr := copy(workerStr, 1, 1);
      result := copy(workerStr, 2, 1) + result;
    end
    else
    begin
      result := inttostr(worker) + result;
      carryStr := '0';
    end;


    inc(i);
  end; { while }
  if carryStr <> '0' then
    result := carryStr + result;
end;

This function will multiply two numbers that are represented by their string digits:

function MultiplyNumStrings (Str1, Str2 : string): string;
var
  i, j : integer;
  carryStr : string;
  worker : integer;
  workerStr : string;
  tempResult : string;
begin
  Result := '';
  carryStr := '0';
  tempResult := '';

  // process each digit of str1
  for i := 0 to length(Str1) - 1 do
  begin
    while length(tempResult) < i do
      tempResult := '0' + tempResult;

    // process each digit of str2
    for j := 0 to length(Str2) - 1 do
    begin
      worker := (strtoint(copy(Str1, length(str1)-i, 1)) *
                 strtoint(copy(Str2, length(str2)-j, 1))) +
                strtoint (carryStr);
      if worker > 9 then
      begin
        workerStr := inttostr(worker);
        carryStr := copy(workerStr, 1, 1);
        tempResult := copy(workerStr, 2, 1) + tempResult;
      end
      else
      begin
        tempResult := inttostr(worker) + tempResult;
        carryStr := '0';
      end;
    end; { for }
    if carryStr <> '0' then
      tempResult := carryStr + tempResult;
    carryStr := '0';

    result := addNumStrings (tempResult, Result);
    tempResult := '';
  end; { for }

  if carryStr <> '0' then
    result := carryStr + result;
end;

Example: We know the max value for an int64 is 9223372036854775807.
If we multiply 9223372036854775807 x 9223372036854775807 using the above routine we get 85070591730234615847396907784232501249.

Pretty cool, huh?

Answer 3

Performing 2 billion multiplications on huge numbers, in one single thread? Unless you've got a state-of-the-art overclocked CPU cooled with liquid helium, you'd have to wait a whole lot for this to complete. However if you do have, you'd just have to wait for a very long time.

Look what search engines gave out:

• http://www.esanu.name/delphi/Algorithms/Maths/Huge%20numbers.html
• Large numbers in Pascal (Delphi)

if you're lucky, one of them should be enough for this atrocity. If not - good luck finding something.