Get the last 1000 digits of 5^1234566789893943

Question

I saw the following interview question on some online forum. What is a good solution for this?

Get the last 1000 digits of 5^1234566789893943

Answer 1

Simple algorithm:

1. Maintain a 1000-digits array which will have the answer at the end
2. Implement a multiplication routine like you do in school. It is O(d^2).
3. Use modular exponentiation by squaring.

Iterative exponentiation:

array ans;
int a = 5;

while (p > 0) {

    if (p&1) {

       ans = multiply(ans, a)
    }

    p = p>>1;

    ans = multiply(ans, ans);
}

multiply: multiplies two large number using the school method and return last 1000 digits.

Time complexity: O(d^2*logp) where d is number of last digits needed and p is power.

Answer 2

A typical solution for this problem would be to use modular arithmetic and exponentiation by squaring to compute the remainder of 5^1234566789893943 when divided by 10^1000. However in your case this will still not be good enough as it would take about 1000*log(1234566789893943) operations and this is not too much, but I will propose a more general approach that would work for greater values of the exponent.

You will have to use a bit more complicated number theory. You can use Euler's theorem to get the remainder of 5^1234566789893943 modulo 2^1000 a lot more efficiently. Denote that r. It is also obvious that 5^1234566789893943 is divisible by 5^1000.

After that you need to find a number d such that 5^1000*d = r(modulo 2^1000). To solve this equation you should compute 5^1000(modulo 2^1000). After that all that is left is to do division modulo 2^1000. Using again Euler's theorem this can be done efficiently. Use that x^(phi(2^1000)-1)*x =1(modulo 2^1000). This approach is way faster and is the only feasible solution.

Answer 3

The technique we need to know is exponentiation by squaring and modulus. We also need to use BigInteger in Java.

Simple code in Java:

BigInteger m = //BigInteger of 10^1000

BigInteger pow(BigInteger a, long b) {
   if (b == 0) {
      return BigInteger.ONE;
   }
   BigInteger val = pow(a, b/2);
   if (b % 2 == 0)
       return (val.multiply(val)).mod(m);
   else
       return (val.multiply(val).multiply(a)).mod(m);
}

In Java, the function modPow has done it all for you (thank Java).

Answer 4

The key phrase is "modular exponentiation". Python has that built in:

Python 3.4.1 (v3.4.1:c0e311e010fc, May 18 2014, 10:38:22) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> help(pow)
Help on built-in function pow in module builtins:

pow(...)
    pow(x, y[, z]) -> number

    With two arguments, equivalent to x**y.  With three arguments,
    equivalent to (x**y) % z, but may be more efficient (e.g. for ints).

>>> digits = pow(5, 1234566789893943, 10**1000)
>>> len(str(digits))
1000
>>> digits
4750414775792952522204114184342722049638880929773624902773914715850189808476532716372371599198399541490535712666678457047950561228398126854813955228082149950029586996237166535637925022587538404245894713557782868186911348163750456080173694616157985752707395420982029720018418176528050046735160132510039430638924070731480858515227638960577060664844432475135181968277088315958312427313480771984874517274455070808286089278055166204573155093723933924226458522505574738359787477768274598805619392248788499020057331479403377350096157635924457653815121544961705226996087472416473967901157340721436252325091988301798899201640961322478421979046764449146045325215261829432737214561242087559734390139448919027470137649372264607375942527202021229200886927993079738795532281264345533044058574930108964976191133834748071751521214092905298139886778347051165211279789776682686753139533912795298973229094197221087871530034608077419911440782714084922725088980350599242632517985214513078773279630695469677448272705078125
>>> 

Answer 5

Use congruence and apply modular arithmetic. Square and multiply algorithm. If you divide any number in base 10 by 10 then the remainder represents the last digit. i.e. 23422222=2342222*10+2

So we know:

5=5(mod 10)
5^2=25=5(mod 10)  
5^4=(5^2)*(5^2)=5*5=5(mod 10)
5^8=(5^4)*(5^4)=5*5=5(mod 10)

... and keep going until you get to that exponent

OR, you can realize that as we keep going you keep getting 5 as your remainder.

Answer 6

Convert the number to a string.

Loop on the string, starting at the last index up to 1000.

Then reverse the result string.

Answer 7

I posted a solution based on some hints here.

#include <vector>
#include <iostream>

using namespace std;

vector<char> multiplyArrays(const vector<char> &data1, const vector<char> &data2, int k) {
    int sz1 = data1.size();
    int sz2 = data2.size();
    vector<char> result(sz1+sz2,0);

    for(int i=sz1-1; i>=0; --i) {
        char carry = 0;
        
        for(int j=sz2-1; j>=0; --j) {
            char value = data1[i] * data2[j]+result[i+j+1]+carry;  
            
            carry = value/10;            
            result[i+j+1] = value % 10;
        }

        result[i]=carry;
    }
    if(sz1+sz2>k){
        vector<char> lastKElements(result.begin()+(sz1+sz2-k), result.end());
        return lastKElements;
    }
    else
        return result;
}

vector<char> calculate(unsigned long m, unsigned long n, int k) {
    if(n == 0) {
        return vector<char>(1, 1);
    } else if(n % 2) { // odd number
        vector<char> tmp(1, m);
        vector<char> result1 = calculate(m, n-1, k);
        return multiplyArrays(result1, tmp, k);
    } else {
        vector<char> result1 = calculate(m, n/2, k);
        return multiplyArrays(result1, result1, k);
    }
}

int main(int argc, char const *argv[]){


    vector<char> v=calculate(5,8,1000);
    for(auto c : v){
        cout<<static_cast<unsigned>(c);
    }

}

Answer 8

I don't know if Windows can show a big number (Or if my computer is fast enough to show it) But I guess you COULD use this code like and algorithm:

ulong x = 5; //There are a lot of libraries for other languages like C/C++ that support super big numbers. In this case I'm using C#'s default `Uint64` number.
for(ulong i=1; i<1234566789893943; i++)
{
    x = x * x; //I will make the multiplication raise power over here
}
string term = x.ToString(); //Store the number to  a string. I remember strings can store up to 1 billion characters.

char[] number = term.ToCharArray(); //Array of all the digits
int tmp=0;
while(number[tmp]!='.') //This will search for the period.
tmp++;

tmp++; //After finding the period, I will start storing 1000 digits from this index of the char array

string thousandDigits = ""; //Here I will store the digits.

for (int i = tmp; i <= 1000+tmp; i++)
{
    thousandDigits += number[i]; //Storing digits
}

Using this as a reference, I guess if you want to try getting the LAST 1000 characters of this array, change to this in the for of the above code:

string thousandDigits = "";

for (int i = 0; i > 1000; i++)
{
    thousandDigits += number[number.Length-i]; //Reverse array... ¿?
}

As I don't work with super super looooong numbers, I don't know if my computer can get those, I tried the code and it works but when I try to show the result in console it just leave the pointer flickering xD Guess it's still working. Don't have a pro Processor. Try it if you want :P