Linked Questions

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

To speed up my bignum divisons I need to speed up operation y = x^2 for bigints which are represented as dynamic arrays of unsigned DWORDs. To be clear: DWORD x[n+1] = { LSW, ......, MSW }; where n+1 ...

As a hobby project I'm taking a crack at finding really large prime numbers. The primality tests for this contain modular exponentiation calculations, i.e. a^e mod n. Let's call this the modpow ...

I've been trying to find some places to help me better understand DFT and how to compute it but to no avail. So I need help understanding DFT and it's computation of complex numbers. Basically, I'm ...

I'm trying to write a C program which performs multiplication of two numbers without directly using the multiplication operator, and it should take into account numbers which are sufficiently large so ...

Arbitary-precision signed integers are almost always implemented using a sign-magnitude representation: (Java) BigInteger in OpenJDK (Python) Bigint implementation of the Python built-in int type in ...

I have written a BigInteger class in C++ that should be able to do operations on all numbers with any size. Currently I am trying to achieve a very fast multiplication method by comparing the existing ...

Given an array A of integers of size N, I want to compute This was a problem in a past inter-college programming competition. We had to write a program that would solve up to 5 instance of this ...

Good afternoon! I am trying to develop an NTT algorithm based on the naive recursive FFT implementation I already have. Consider the following code (coefficients' length, let it be m, is an exact ...

I have given two number a and b.I have to Calculate (a^b)%1000000007.How Can i calculate for floating point numbers. Ex: a= 7.654 and b=10000 Here is my Code will % work : public static double ...

I want to calculate for very large numbers like n = 10^15. Somehow I can't, because of OverflowError. xd = lambda n : ((((5+ sqrt(17)) * ((3 + sqrt(17)) ** n)) - ((5-sqrt(17))* ((3 - sqrt(17)) ** n)))/...

I am working on a project right now where I need to perform calculations for numbers with base 256. I am reading bytes of a file and storing it in an array of uint8_t (a.k.a unsigned char or BYTE). ...

I am given with three integers A, B and C. I need to implement a program to perform the operation A^B modulus C. I without thinking much, wrote the following code:- public int Mod(int A, int B, int C) ...

I have to find c, c = (a*b) mod m a,b,c,m are 32-bit integers. But (a*b) can be more than 32 bits. I am trying to figure out a way to compute c, without using long or any data type > 32 bit. Any ...

I would like to implement multiplication of polynomials using NTT. I followed Number-theoretic transform (integer DFT) and it seems to work. Now I would like to implement multiplication of ...