Loading ...
Sorry, an error occurred while loading the content.
 

mulmod64...

Expand Messages
  • David Cleaver
    Hello all, I ve looked around the net for some code that implements mulmod(a,b,c) (ie, a*b mod c, where a,b,c are all unsigned 64-bit integers), but haven t
    Message 1 of 1 , Jun 29, 2009
      Hello all,

      I've looked around the net for some code that implements mulmod(a,b,c) (ie, a*b
      mod c, where a,b,c are all unsigned 64-bit integers), but haven't found any code
      that works for all inputs. By all inputs, I mean:
      0 <= a <= 2^64-1
      0 <= b <= 2^64-1
      2 <= c <= 2^64-1

      I saw online how a few years ago Phil Carmody talked about this on another forum
      and how Jack Brennan asked on this list. Did you two ever come up with code to
      work for all inputs? I've tried the floating point versions I've seen online,
      but those are failing for large values of a and b near 2^64.

      If anyone could give me a pseudocode outline of an algorithm, or better still
      actual C code, or even better still optimized x86 assembly, that'd be great! If
      anyone knows of a book or an article detailing such code, I'd like to hear about
      those as well. Thanks for your time.

      -David C.
    Your message has been successfully submitted and would be delivered to recipients shortly.