Incorrect Modulo Calculation

[GoogleCodeExporter]

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)

Original issue reported on code.google.com by armin.widegreen@gmail.com on 1 Jul 2009 at 1:16

[GoogleCodeExporter]

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.

Original comment by wolf.lam...@googlemail.com on 1 Jul 2009 at 3:46

[GoogleCodeExporter]

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! 

Original comment by armin.widegreen@gmail.com on 1 Jul 2009 at 4:08

[GoogleCodeExporter]

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.

Original comment by zan...@gmail.com on 15 Jan 2010 at 6:35

[GoogleCodeExporter]

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

Original comment by wolf.lam...@googlemail.com on 16 Jan 2010 at 1:58

[GoogleCodeExporter]

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

Original comment by wes...@gmail.com on 18 Jun 2010 at 7:21

[GoogleCodeExporter]

Original comment by helder.p...@gmail.com on 17 Dec 2014 at 9:56

• Added labels: Type-Defect