Reducing the operation by using the modulo

paut · Nov 7, 2011

Hi, I wonder that is there any way to disassemble this operation ((n+2^(n-2))^2 mod 1000000007) without counting 2^n-2. Please, help me.

I like Serena · Nov 7, 2011

Welcome to PF, paut!

Well, if n<15, then the result is simply the same, since it would be less than 1000000007.
For larger numbers you can reduce the power by using that (2^1000000006 mod 1000000007)=1.

dodo · Nov 8, 2011

Another possibility is to perform the entire calculation using modular arithmetic algorithms. That is, your expression can be calculated as:

r1 = modular_exponentiation of 2 to the n-2, performed modulo 1000000007
r2 = r1 + n, modulo 1000000007
r3 = modular_exponentiation of r2 to the 2, performed modulo 1000000007

and your result is r3.

Google for "modular exponentiation algorithm"; a method simple to implement is the "russian peasant algorithm" (google for that).

In order to implement this, you'll need another method for modular multiplication, because calculating (a * b) % 1000000007 will likely give you an overflow in the a*b product, before you get to reduce it modulo 1000000007. But that is not hard to devise (shifting and adding), or google again for "peasant multiplication" and adapt it with a modulo 1000000007 at each step. (You'll see what I mean when you get hands-on into it.)

There are of course more complicated algorithms (of which I can't speak because I don't really know), but the above are manageable simple.

paut · Nov 8, 2011

"mod_pow" is a function (using fast modular exponentiation) which returns the result of exponentiation modulo 1000000007 - mod_pow (the first parameter, second parameter, modulo). The first parameter is the base, and the second parameter is the exponent.

For:
y <- n + mod_pow (2, n-2, 1000000007).
result <- mod_pow (y, 2, 1000000007).

I get an incorrect result, so I had misunderstood something. Very please to explain.

dodo · Nov 9, 2011

Can you show the code for mod_pow? It may have an error, or maybe it is designed to work with a parameter value which is already under 1000000007 (and "y", on the second call, is not).

I like Serena · Nov 9, 2011

paut said: ↑

"mod_pow" is a function (using fast modular exponentiation) which returns the result of exponentiation modulo 1000000007 - mod_pow (the first parameter, second parameter, modulo). The first parameter is the base, and the second parameter is the exponent.

For:
y <- n + mod_pow (2, n-2, 1000000007).
result <- mod_pow (y, 2, 1000000007).

I get an incorrect result, so I had misunderstood something. Very please to explain.

Your formulas look right.
If it does not work, I expect an overflow, which would typically occur on a 32 bits platform.
What is your platform?
What is your computer language?
What is the type of the parameters to mod_pow?
What is the type of the variables you use to calculate?

paut · Nov 9, 2011

From the beginning I should explain what I want to achieve.

My work for the sequences of length 'n' is finding a number of variations elements of two-piece set, in this way that one of this two elements (doesn't matter which) will never occure next to another.
If set is composed just of '0' and '1' then possible combinations looks like this (I assume that element that will never appear next to another is ‘1’):
For n=2: 00 01 10 (result – 3)
For n=3: 000 001 010 100 101 (result - 5)
For n=4: 0000 0001 0010 0100 1000 1010 0101 1001 (result – 8)

I have to show result as: result^2 mod 1000000007. Maximum of 'n' is 2^31 -1 that is 2147483647. Maximum of calculating time is 1s.

One of my problems is to find a formula that gives me a number of combinations. I noticed some dependency between another results and I created a formula n+2^(n-2) for n>1, unfortunately I'm not 100% sure that this formula is correct ( I checked that for low 'n' this formula is correct).

My another problem is displaying a huge numbers. If n=2000000000 then calculating 2^(n-2) become impossible because of the size of result. However doing the calculations on string takes a lot of time.
Because of this it became obvious for me that I need to use fact that the final result have to be modulo 1000000007. At the beginning I turned in this forum with this problem.

On the web I found two implementations of modular exponentiation :

1: „unsigned long long int mod_pow(unsigned long long int num, unsigned long long int pow, unsigned mod)
{
　　unsigned long long int test,n=num;
　　for(test = 1; pow; pow >>= 1)
　　{
　　　　if (pow & 1)
　　　　　　test = ((test % mod) * (n % mod)) % mod;
　　　　n = ((n % mod) * (n % mod)) % mod;
　　}

　　return test;
}”

2: „unsigned long long int power_modulo_fast(unsigned long long int a, unsigned long long int b)
{
　　unsigned long long int x=a%1000000007,result=1,i;
　　for (i=1; i<=b; i<<=1)
　　{
　　　　x %= 1000000007;
　　　　if ((b&i) != 0)
　　　　　　{
　　　　　　　　result *= x;
　　　　　　　　result %= 1000000007;
　　　　　　}
　　　　x *= x;
　　}
　　return result;
}”

The final code is tested on the internet checker not on my computer, so parameters of my computer really doesn't matter.

I wrote a program for test which operating on strings so exponentiation 2^1000 isn't problem, but when I'm testing this program on my computer I get other result than those which I recived after using the above functions. Unfortunately I can't take this program as my official solution of this problem, because calculations takes a lot of time for higher data like n=1000000.

dodo · Nov 9, 2011

From what I can see at first glance, the code for these two functions looks fine; but you may want to check that, in your machine and C compiler, "sizeof (long long int)" returns 8 (8 bytes = 64 bits).

In case this helps, I compared the output of your two functions with my own implementation, and the three of them agree for a few test values of n:

Code (Text):

Evaluations of (n + 2^(n-2))^2 mod 1000000007, for n = ...

2: 9 9 9
3: 25 25 25
4: 64 64 64
10: 70756 70756 70756
20: 729962420 729962420 729962420
456: 781936176 781936176 781936176
456000: 832296930 832296930 832296930
4560000: 786542175 786542175 786542175
45600000: 98463981 98463981 98463981
456000000: 494805060 494805060 494805060
500000005: 250000008 250000008 250000008
1000000008: 4 4 4

For n=2,3,4,10,20,456,456000 and 4560000, I also checked with the Linux multiple-precision calculator "bc", and the result agrees with the above. (For 45600000, 456000000 and 500000005 I didn't check, since "bc" would take too long.) For the last test value, 1000000008, the result 4 is theoretically correct, because of the reason "I like Serena" explained in post#2.

You may want to check these values in your "string" program, too.

P.S.: You may want to google for "arbitrary precision calculator"; a few tools are free to download, and there may even be some to use online on your browser. These could be helpful in checking your results.

P.P.S: Confirmed all values above using the GP/Pari calculator.

paut · Nov 9, 2011

Here are the calculations that should be correct: http://img695.imageshack.us/img695/3950/calcw.png [Broken]

My program returns the same result (the first based on a string and second without them). I also have exactly the same results as you. The problem is probably in the wrong set formula :/ I see no other option :/
Thank you very much for your help which was given to me here ;)

I like Serena · Nov 9, 2011

paut said: ↑

Here are the calculations that should be correct: http://img695.imageshack.us/img695/3950/calcw.png [Broken]

My program returns the same result (the first based on a string and second without them). I also have exactly the same results as you. The problem is probably in the wrong set formula :/ I see no other option :/
Thank you very much for your help which was given to me here ;)

Hmm, I see another option, which is that your results are right.

What is your reason to think that they are wrong?

paut · Nov 9, 2011

I send the source code for online judge, that evaluates the results, but the score for my program is "Wrong answer".

I like Serena · Nov 9, 2011

paut said: ↑

I send the source code for online judge, that evaluates the results, but the score for my program is "Wrong answer".

So let's assume for now that your mod_pow method of evaluation is right (which I think it is).
Is it possible something else is wrong?

paut · Nov 10, 2011

According to my formula for n=7, the number of combinations is 39, but I can’t find so many. If I don't find 39 combinations then the error is in formula.

Combinations which I could find (33):
0000000
0000001 0000010 0000100 0001000 0010000 0100000 1000000
1000001 1000010 1000100 1001000 1010000 0100010 0100001 0101000 0010010 0010100 0010001 0001001 0001010 0000101
1010001 1010010 1010100 0101010 0100101 0101001 1000101 1001010 1001001 0010101
1010101

I like Serena · Nov 10, 2011

I believe the formula for your problem is pretty complex and your current formula does not cover it.
You might search for bernoulli trials and k successes in a row, for more specific information.
(You want all sequences that have at least 2 successes in a row. Or rather, the inverse of that.)

paut · Nov 12, 2011

Ok, I know. This is the Fibonacci series (2,3,5,8,13,21,34 ...).
How can I calculate: fib(n)^2 mod 1000000007, even for very large numbers?

Is it correct? https://ideone.com/cuGkK

I like Serena · Nov 12, 2011

Looks like you already have it down.
And yes, your program looks correct at first sight.
I take it you verified it with a couple of test values?