Incorrect Modulo Calculation

Create issue
Issue #295 new
Former user created an issue

Originally reported on Google Code with ID 295

What steps will reproduce the problem?
1. mod(83^55;221)
2. <Enter>

What is the expected output? What do you see instead?
incorrect calculation: expected 8 (see
http://www.wolframalpha.com/input/?i=83^55+mod+221) but got 144

What version of the product are you using? On what operating system?
Version 0.10.1 on Kubuntu Jaunty (kde 4.3beta2 - ppa version)

Reported by armin.widegreen on 2009-07-01 13:16:25

Comments (10)

  1. Former user Account Deleted

    ``` 83^55 is a number with 106 decimal places - much more than the 80 some digits the engine can hold throughout an evaluation. As a result, a rounded value is fed into the mod operation - leading to your unexpected result. Besides replacing the engine by something more powerful, what can we do here? If mod was only defined on integers, the engine could simply reject an input too big. But mod has been generalized to work on floats as well, so just checking for big numbers would cripple SpeedCrunch in other respects. ```

    Reported by `wolf.lammen` on 2009-07-01 15:46:40

  2. Former user Account Deleted

    ``` i know .. 83^55 is a big number, sorry! ;) But I think, giving the wrong result isn't the best way to handle such big numbers. I don't know how the modulo-computation is implemented now (haven't looked in the sources), but maybe the "binary exponentiation" could be a smarter way (for ints) - if it isn't yet!

    ```

    Reported by `armin.widegreen` on 2009-07-01 16:08:14

  3. zanetu NA

    ``` Hi, I just encountered the same problem when trying out RSA examples. In RSA cryptosystem, modular calculation on such large numbers are quite common. :) I agree with armin.widegreen as to the inappropriateness of giving the wrong result. Is it a good idea to create a new function (eg modf) that is dedicated to floats and prompts the user to use the new function when he or she tries to use mod on floats? After all, integers are far more frequently used than floats in modular calculation and the correctness of integer calculation should be given first priority.

    ```

    Reported by `zanetu` on 2010-01-15 06:35:33

  4. Former user Account Deleted

    ``` Speedcrunch essentially has a 'single-data-type' engine and this type is fixed to an 80 decimal digits floating point format. Built-in support for integers is very limited, covering just a few bitwise operations like AND or XOR. Prior to their execution, operands are converted to 256 bit integers, and results finally converted back to native floating point format. While I understand there is occasionally specialized need for arbitrary precision integer arithmetic, (as far as I am concerned) Speedcrunch in near future will not serve these needs, because it requires - a complete rewrite of the engine - a paradigm change in user interface, requesting users to be aware of and deal with the concept of a data type.

    You can do integer arithmetic as long as you do not pass by the 256 bit limit. If you do, Speedcunch silently uses the floating point style arithmetic it was once designed for. 256 bit is enough for all every-day needs of computer scientists. Demands of cryptology require something different.

    cheers Wolf ```

    Reported by `wolf.lammen` on 2010-01-16 13:58:10

  5. Former user Account Deleted

    ``` But you can always set a bigger limit in floatconfig.h (MAXDIGITS, DECPRECISION, MATHPRECISION) and even mod(83^100;221) works fine :)

    ```

    Reported by `wesand` on 2010-06-18 07:21:11

  6. Former user Account Deleted

    Reported by helder.pereira.correia on 2014-12-17 21:56:33 - Labels added: Type-Defect

  7. Pol Welter

    The best solution would without doubt be the implementation of modular exponentiation in a function called powmod(a, n, p).

  8. Log in to comment