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

Tetryl

Hint: Exponentiation by squaring – Lacilacie

as mentioned in some answers here modpow is your answer just need to add, x=modpow(5,1234566789893943,10^1000) and take in mind the result is ~3322 bit long (log10(10^1000)/log10(2)=1000/0.30103) so use bigint or string numbers with big enough bits/digis to avoid overflows during computation – Importation

few use-able links for this task fast sqr: https://mcmap.net/q/296896/-fast-bignum-square-computation/2521214 , NTT+modpow: https://mcmap.net/q/591397/-modular-arithmetics-and-ntt-finite-field-dft-optimizations/2521214 and if you want to use binary number representation then also fast dec<->hex conversions: https://mcmap.net/q/121025/-how-to-convert-a-gi-normous-integer-in-string-format-to-hex-format-c – Importation

Solve the congruence system x = 5^443 (mod 2^1000) and x = 0 (mod 5^1000) using the Chinese remainder theorem. – Merilee

If you can't solve the problem on paper, then you can't solve the problem with a computer. Think. – Glamorize

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.

Monostich

How long do you think it will take to do this computation even on the fastest computer? – Slum

@IvayloStrandjev its is O(d^2*logp) which can be optimized using packing into integer but it can only be bettered using karatsuba multiplication O(d^1.5*logp) which is more complex so i think it fairly fast and simple for a solution to interview – Monostich

Take a look at my answer. The computation can be significantly optimized but requires harder theory. My point is that even on the fastest computer this approach would take many,many centuries – Slum

@IvayloStrandjev sorry but my solution is generic and would evaluate for any (a,p) pair without assumption . Moreover it wont take centuries as you claim for above example it takes about 1000^2*log(1234566789893943) iterations which is 5*10^7 would happen within seconds on reasonable computer – Monostich

Ahh sorry my mistake I have computed the number of operations incorrectly. I will remove my answer as it is far too complicated(although still general enough) – Slum

@IvayloStrandjev no need for removing your answer i think it is very smart. – Monostich

Actually you are right. I will keep it as it works for way higher exponents. Still your answer is more appropriate – Slum

Just one comment on the "school multiplication". Here we can cut the corners as we are not interested in the first 1000 digits (1000x1000->2000 digit multiplication). This cuts the time by half. – Sorayasorb

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.

Slum

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).

Ethnology

@VikramBhat that true, ha ha, look at the question so fast :D – Ethnology

+1 correct answer but i doubt you are given an option to use the libraries in interview – Monostich

@VikramBhat That' s true, I think this can be a bonus point if you can point it out after explaining how to do it :) – Ethnology

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
>>> 

Eyed

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.

Corell

OP needs the answer (mod 10^1000), not (mod 10). – Voyeurism

Oh yes, thanks for pointing that out my bad. Well the idea is the same in that case but you just have a larger modulus. – Corell

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.

Donndonna

and how you can calculate a number which must be stored at least on ~3000 (three thousands) bits? can we use a 64bits double or a 32bits float? I'm so confused, but the 64 bits are a bit closer to 3000 bits, than 32 bits, I guess... – Viradis

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);
    }

}

Tetryl

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

Payola

This is wrong. 5^1234566789893943 is way bigger than 2^64. so it will overflow in a 64 bit int. – Iormina

@MartínFixman I think you have problems of attention. At least did you read what I put before the code? lol – Payola

There's simply no computer that can handle a ~536165540000000 bit int, necessary to compute 5^1234566789893943. – Iormina

Again. Did you read the FIRST paragraph of what I said? @MartínFixman – Payola

"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:"? Windows can't show such a big number, your computer isn't fast enough to show it, and OP couldn't use this algorithm. – Iormina

@MartínFixman again... Did you learn to read? you COULD use this code like and algorithm As I said, LIKE AN ALGORITHM... Damn... You programmers are so fcked up when reading... You don't know to read lol – Payola