Rules for applying mod

Jaini_sof 2011-03-17 17:46:36 UTC #1

hi all

i have problem on working with mod operation on big numbers.

e.g
(a+b)%10000000007 where a and b are both unsigned long long in cpp

both a and b are near to LLONG_MAX.
value of both are being changed by some fixed operation like multiplication iteratively.

Now i am confused in following.is it right or not?
(a+b)%10000000007=a%10000000007+b%10000000007

and same thing with multiplication
(a*b)%10000000007=(a%10000000007)*(b%10000000007)

please help me in this concept.

With Regards
Jaini

kokosek 2011-03-17 19:40:58 UTC #2

No but You're close.
That's the correct formula:
(a+b)%10000000007=(a%10000000007+b%10000000007)%10000000007

Because assume that a=b=9999999999.
(a+b)%10000000007=19999999998%10000000007=9999999991
And a%10000000007+b%10000000007=a+b=19999999998

Jaini_sof 2011-03-18 17:22:27 UTC #3

thanks for you answer

please tell me
can i use it to calculate 10 raise to power 18th fibonacci no. using following

matrix form

kokosek 2011-03-18 20:29:51 UTC #4

I may not understand.
The formula You've written allows You to calculate the next Fibonacci number.
The complexity is O(n), then (it anybody disagree please correct me).
I don't understand what does it have in common with "modulo trick" and 10-power.
Sorry for my ignorance if I don't know the algorithm You want to use.

Jaini_sof 2011-03-19 04:26:23 UTC #5

actually i need to find out (nth fibonacci no.) % 10000000007 and that n can be 10^18.

sorry ,i wrote wrong formula i'm using following

F(x+2) (1 1)^x (1)
=
F(x+1) (1 0) (1)

understand it wrt matrix form(no good way to represent matrix here.. )

modulo trick is needed because matrix element would be multiplied and thus can go beyond maximum limit of LONG_MAX.

kokosek 2011-03-19 09:25:39 UTC #6

If You have to deal with so big numbers, is Your formula fast enought?
Because with this range of n even O(n) is too slow.

// I think FAQ isn't a good section for this kind of problems.

Jaini_sof 2011-03-19 13:46:52 UTC #7

my algorithm is of O(log n) complexity..

kokosek 2011-03-19 14:04:55 UTC #8

If so, it's fine.
Good luck with the task.