it is possible your implementation would be more memory efficient, but less time efficient. If the built-in way runs in one microsecond, but yours takes one second, then time will become more important than memory.
I have no idea if this will actually be the case, but it is something to at least consider.
Never ascribe to malice that which can be adequately explained by stupidity.
Yeah, Immutables are not good when you are doing large volume operations. That is one of the reasons why Java tells you to use StringBuffer/StringBuilder instead of String when you are dealing with large number of String operations.
Joined: Mar 24, 2005
So I did some googling and here's what I found (hope it helps - I believe it will, since AxB is a huge number, as you mentioned, but (A mod n)x(B mod n) should be much smaller):
A very similar development can be used to show that the modulo operator replicates over multiplication.
Given the expression
c = (ab) mod n
we could, of course, evaluate it directly. But we can also invoke the definition of a residue as follows:
a = kan + ra
b = kbn + rb
Where ka and kb are appropriate integers and ra and rb are the residues of a and b respectively. Hence
c = ( ( kan + ra )( kbn + rb) ) mod n
c = ( (kakb)n2 + (rakb + rbka)n + (rarb) ) mod n
We can then replicate the modulo operator over the sum of terms yielding
c = ( ((kakb)n2 mod n ) + ((rakb + rbka)n mod n) + ((rarb) mod n) ) mod n
Since the first two terms contain n as a factor their residues are zero, leaving
c = ( (rarb) mod n) ) mod n
The second modulo operation is redundant and can be removed.
c = (rarb) mod n
We also have, by definition,
ra = a mod n
rb = b mod n
Combining all of this, we get the following property of modular addition:
Right. To put Geoffrey's problem another way, A and B are 1-digit numbers in base M. So when you multiply them you get a 2-digit number, of which you only require the second digit. This is a potential problem for Geoffrey because M is a large number.
Unfortunately the technique posted by Emanuel starts by reducing A and B to their last digits in the base-M representation, which is the correct general solution but doesn't help in this particular case.
If you put M = 10 just for ease of thinking about the problem, it's asking (for example) how to calculate that 6 x 7 ends in 2 without having to evaluate 42 at any time in the calculation.
Paul Clapham wrote:If you put M = 10 just for ease of thinking about the problem, it's asking (for example) how to calculate that 6 x 7 ends in 2 without having to evaluate 42 at any time in the calculation.
One way to do that is to replace the multiplication by repeated addition, applying mod-M at each step. This means that the largest number you ever use in the calculation is of the order of 2M, rather than M^2. However as fred warned, this algorithm is likely to be much slower than the plain old multiply and reduce mod M algorithm. Not to mention that if the issue is garbage collection of temporary objects used in the calculation, this algorithm is likely to produce a lot more temporary objects which are somewhat smaller.