How to calculate division remainder of 64bit integer given as string in Javascript

Question

Is there fast and simple way to make an "%" operation for 64bit integer given as "string" (for example "1bed658e4cbba3a7")?

I know that Google Closure Library has such function, but I'd prefer not to use any external libraries, and moreover internally it works as three operations (division, multiplication and substraction) and seems to be not optimal.

Added: Problem is that JavaScript cannot handle 64bit integers without loosing precision. For details see this question

Didn't get the question, what is the "%" operator? what do you want to accomplish? — gdoron, Nov 12 '12 at 16:05
A 64-bit integer will lose precision if you convert it to a JS `Number` (not the number in your example, but any int where `abs(int) > 2^53`, I believe) — NullUserException, Nov 12 '12 at 16:07
Why not use that library if it does exist? And no, there is no simple way :-) — Bergi, Nov 12 '12 at 20:29

score 3 · Accepted Answer · answered Nov 12 '12 at 21:52

If you have an upper bound on the right-hand operand, then you can split the 64-bit int into two parts, and calculate the modulus from that. (It's three % operations, and I don't know whether that's fast enough for your purposes).

For example, if you want to calculate x % c, and c < 2^32, then you can split x into two parts, a and b, and calculate:

(a * 2^32 + b) % c = (((a % c)* (2^32 % c)) + b) % c

This depends on c being small, though. If it is also close to 64 bits, then you will want to look for other methods.

Thanks, Ian! It seems to be the best solution for my purposes. But can you point me at the math background? Why is this expression looks like it looks? — accme, Nov 12 '12 at 22:19

How to calculate division remainder of 64bit integer given as string in Javascript

1 Answers1