1

I am finding pow(2,i) where i can range: 0<=i<=100000. Apart i have MOD=1000000007

powers[100000];
powers[0]=1;
for (i = 1; i <=100000; ++i)
{
  powers[i]=(powers[i-1]*2)%MOD;
}

for i=100000 won't power value become greater than MOD ?

How do I store the power correctly?

The operation doesn't look feasible to me. I am getting correct value up to i=70 max I guess.

I have to find sum+= ar[i]*power(2,i) and finally print sum%1000000007 where ar[i] is an additional array with some big numbers up to 10^5

Kabhi
  • 135
  • 1
  • 12
  • 4
    There's one obvious and glaring problem with the code as shown, and that is that you have forgotten that arrays of size X have indexes from zero t0 X *minus one*, so the highest index for your `powers` array is `99999`. – Some programmer dude May 18 '15 at 06:49
  • You probably want a [bignum](http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic) library like [GMPlib](http://gmplib.org/) – Basile Starynkevitch May 18 '15 at 06:58
  • 1
    possible duplicate of [Calculating pow(a,b) mod n](http://stackoverflow.com/questions/8496182/calculating-powa-b-mod-n) – Pham Trung May 18 '15 at 07:18
  • to determine what correctly means we need more context. Fe. if the only task is to store the numbers, you don't even need the array. – wonko realtime May 18 '15 at 07:22
  • I just made a few tests; this code seems to work perfectly well for me even for `i=99999`. The modulo operation in each iteration ensures that you will not get any overflow. What did you mean by "getting correct value up to `i=70`"? – jadhachem May 18 '15 at 07:26
  • I believe OP thought that `for i=100000 power value will become greater than MOD`, but this is wrong, (a % b) <= b in any case. – Pham Trung May 18 '15 at 07:29
  • Yes, I think the OP's misunderstanding here is that the powers are calculated with [modular arithmetic](http://en.wikipedia.org/wiki/Modular_arithmetic) and that you can't get the real powers from the modular values. – M Oehm May 18 '15 at 07:37

2 Answers2

2

As long as your modulus value is less than half the capacity of your data type, it will never be exceeded. That's because you take the previous value in the range 0..1000000006, double it, then re-modulo it bringing it back to that same range.

However, I can't guarantee that higher values won't cause you troubles, it's more mathematical analysis than I'm prepared to invest given the simple alternative. You could spend a lot of time analysing, checking and debugging, but it's probably better just to not allow the problem to occur in the first place.

The alternative? I'd tend to use the pre-generation method (having a program do the gruntwork up front, inserting the pre-generated values into an array easily and speedily accessible from your real program).

With this method, you can use tools that are well tested and known to work with massive values. Since this data is not going to change, it's useless calculating it every time your program starts.

If you want an easy (and efficient) way to do this, the following bash script in conjunction with bc and awk can do this:

#!/usr/bin/bash

bc >nums.txt <<EOF
    i = 1;
    for (x = 0;x <= 10000; x++) {
        i % 1000000007;
        i = i * 2;
    }
EOF

awk 'BEGIN { printf "static int array[] = {" }
           { if (NR % 5 == 1) printf "\n    ";
             printf "%s, ",$0;
             next
           }
     END   { print "\n};" }' nums.txt

The bc part is the "meat" of the matter, it creates the large powers of two and outputs them modulo the number you provided. The awk part is simply to format them in C-style array elements, five per line.

Just take the output of that and put it into your code and, voila, there you have it, a compile-time-expensed array that you can use for fast lookup.

It takes only a second and a half on my box to generate the array and then you never need to do it again. You also won't have to concern yourself with the vagaries of modulo math :-)

static int array[] = {
    1,2,4,8,16,
    32,64,128,256,512,
    1024,2048,4096,8192,16384,
    32768,65536,131072,262144,524288,
    1048576,2097152,4194304,8388608,16777216,
    33554432,67108864,134217728,268435456,536870912,
    73741817,147483634,294967268,589934536,179869065,
    359738130,719476260,438952513,877905026,755810045,
    511620083,23240159,46480318,92960636,185921272,
    371842544,743685088,487370169,974740338,949480669,
    898961331,797922655,595845303,191690599,383381198,
    766762396,533524785,67049563,134099126,268198252,
    536396504,72793001,145586002,291172004,582344008,
    164688009,329376018,658752036,317504065,635008130,
    270016253,540032506,80065005,160130010,320260020,
    640520040,281040073,562080146,124160285,248320570,
    :
    861508356,723016705,446033403,892066806,784133605,
    568267203,136534399,273068798,546137596,92275185,
    184550370,369100740,738201480,476402953,952805906,
    905611805,
};
paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
  • 1
    But isn't `(a*b)%m == ((a%m) * (b%m)) % m`? I get the same result from the all-modulo calculation and from bignum and module (also done with `bc`). – M Oehm May 18 '15 at 07:04
  • @MOehm, your problem is that the intermediate value has an automatic wrap at the word size (modulo some power of two). Let's say your `int` range is `0..255` and you want the modulo `107`. Up to 64, the value mod 107 is the value: `1,2,4,8,16,32,64`. After that, the modulo kicks in but with the right value: `128%107 = 21`. BUT the next power of two is 256. Because you have an 8-bit `int`, that will wrap around to zero when you double `128` and `0 % 107 = 0` whereas what you _wanted_ was `256 % 107 = 42`. Maybe my first paragraph didn't make clear what I was trying to get across so I fixed it. – paxdiablo May 18 '15 at 07:11
  • 1
    @paxdiablo True, but if you're using the post-`mod` value `21`, then doubling that will give you `21 * 2 mod 107 = 42`, which is exactly the value you wanted and avoids any overflow. – jadhachem May 18 '15 at 07:14
  • I'm not convinved. When calculatting 2^8 with modulo arithmetic, I have to work from (2^7) mod 107, of course, not from 128. So I get 2*21, which is 42, the value of (2^8) mod 107. The idea id to use modulo arithmetic with the same modulo value throughout. – M Oehm May 18 '15 at 07:15
  • Actually, that appears to be right. May have to update the answer :-) – paxdiablo May 18 '15 at 07:16
0

If you notice that your modulo can be stored in int. MOD=1000000007(decimal) is equivalent of 0b00111011100110101100101000000111 and can be stored in 32 bits.

 - i      pow(2,i)        bit representation 
 - 0            1         0b00000000000000000000000000000001
 - 1            2         0b00000000000000000000000000000010 
 - 2            4         0b00000000000000000000000000000100 
 - 3            8         0b00000000000000000000000000001000
 - ...
 - 29   536870912         0b00100000000000000000000000000000

Tricky part starts when pow(2,i) is grater than your MOD=1000000007, but if you know that current pow(2,i) will be greater than your MOD, you can actually see how bits look like after MOD

 - i      pow(2,i)  pow(2,i)%MOD      bit representation
 - 30   1073741824  73741817    0b000100011001010011000000000000
 - 31   2147483648  147483634   0b001000110010100110000000000000
 - 32   4294967296  294967268   0b010001100101001100000000000000
 - 33   8589934592  589934536   0b100011001010011000000000000000

So if you have pow(2,i-1)%MOD you can do *2 actually on pow(2,i-1)%MOD till you're next pow(2,i) will be greater than MOD.

In example for i=34 you will use (589934536*2) MOD 1000000007 instead of (8589934592*2) MOD 1000000007, because 8589934592 can't be stored in int.

Additional you can try bit operations instead of multiplication for pow(2,i). Bit operation same as multiplication for 2 is bit shift left.

M.L.
  • 728
  • 4
  • 12
  • i have two find sum+= ar[i]*power(2,i) and finally print sum%1000000007 where ar[i] is an additional array with some big numbers up to 10^5. if i return pow%MOD from the method you telling, won't my sum be incorrect ? – Kabhi May 18 '15 at 09:22
  • Edit your question, so everyone could answer. Clarify what you're want to accomplish. – M.L. May 18 '15 at 09:26