Hi to everyone,(adsbygoogle = window.adsbygoogle || []).push({});

i'm writing a program in C that is supposed to run on a AVR processor with registers and int of 16 bit (like the one used in some sensor for WSN). This program involves the use of the Lagrange Interpolation. I've worked on it managing to solve most part of the problems but i'm still facing a pure mathematical issue.

Basically all my values are now smaller than 2^16 (they're stored modulus 2^16) but when i multiply two of that values an overflow can occur since the avr-gcc compiler (with the setting i'm using) is not capable of handling any values bigger than 2^16.

So the question is: "Givenaandbsmaller than 2^16 is there an efficient method to obtain(a*b) mod nwithout using any variable longer than 16 bit?".

In a normal situation i would have simply used a double lenght variable (32 bit in this case) to hold the producta*bthen applied the modulus. In this case I can't store any values bigger than 16 bit so i need an efficient alghoritm to compute(a*b) mod nunder these costraints.

I cannot use any C++ class or anything different from standard C instructions.

Thank you in advance for all the answers,

Lu

**Physics Forums - The Fusion of Science and Community**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Modular multiplication problem in C

Loading...

Similar Threads - Modular multiplication problem | Date |
---|---|

Is there such a thing as multiple simulation? | Sep 21, 2017 |

Matrix Chain Multiplication: Optimal way of multiplying | Feb 26, 2017 |

Java Problem with code, possibly multiple extensions of JFrame | Feb 14, 2017 |

The advantage of modular arithmetic, e.g. cyclic groups? | Nov 17, 2014 |

Modular Multiplication | Dec 29, 2006 |

**Physics Forums - The Fusion of Science and Community**