First the problem.
Z ==> Integer
SI ==> SingleInteger
p:=prevPrime((max()$SI)::Z)$IntegerPrimesPackage(Z)
F ==> PrimeField p
FZ ==> SUP F
f: FZ := monomial(1, 2)$FZ - 2
factor(f)
If running this in a session one ends up with a nasty
(6) -> f: FZ := monomial(1, 2)$FZ - 2
Compiling function G387 with type Integer -> Boolean
Compiling function G389 with type NonNegativeInteger -> Boolean
2
(6) ? + 4611686018427387845
Type:
SparseUnivariatePolynomial(PrimeField(4611686018427387847))
(7) -> factor(f)
>> System error:
The value
4684986446884335550
is not of type
FIXNUM
That's probably not a very big surprise when looking at the special
implementation of a finite field for a prime that is just a bit smaller
than the maximum size of a SingleInteger.
However, of course, that shouldn't happen.
I first thought that the multiplication in PrimeField is problematic,
but no, it works fine. The problem is addmod $ SingleInteger.
See session below.
The documentation for addmod of SingleInteger is inherited from
IntegerNumberSystem.
addmod: (%, %, %) -> %
addmod(a, b, p), 0<=a, b<p>1, means a+b mod p.
Well, one might probably expect that there are problems if the domain
has only the size of a lisp fixnum. But that's certainly implementation
dependent. And seemingly mulmod works just fine for these border cases.
Although, I would somehow like that the ++ docstring for addmod $
SingleInteger would mention the restriction that not only a<p, b<p, but
also a+b<=max(), I can live with the implicit restriction, that a
programmer has to take care in the SingleInteger case.
However, there is a real bug that results from this restriction and that
is in IntegerMod(p)
It says
if p <= convert(max()$SingleInteger)@Integer then
Rep := SingleInteger
q := p::SingleInteger
...
else
Rep := Integer
...
Of course it should rather say:
if p <= convert(shift(max()$SingleInteger, -1))@Integer then
Bugfix is attached.
Can I commit?
Ralf
(1) -> I ==> SingleInteger
(2) -> p: I := max()$I -123456
(2) 4611686018427264447
Type: SingleInteger
(3) -> a: I := p - 1
(3) 4611686018427264446
Type: SingleInteger
(4) -> b: I := shift(a, -1)+100
(4) 2305843009213632323
Type: SingleInteger
(5) -> a + a
>> System error:
The value
9223372036854528892
is not of type
FIXNUM
(5) -> b + b
(5) 4611686018427264646
Type: SingleInteger
(6) -> addmod(a, a, p)
>> System error:
The value
9223372036854528892
is not of type
FIXNUM
(6) -> addmod(b, b, p)
(6) 199
Type: SingleInteger
(7) -> mulmod(a, a, p)
(7) 1
Type: SingleInteger
(8) -> mulmod(a, b, p)
(8) 2305843009213632124
Type: SingleInteger
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/fricas-devel/13d47e96-0def-cb1e-aae6-2402b04e8c8b%40hemmecke.org.
From 3eedeffb866913d3cdb4d2150ce3d13380117e69 Mon Sep 17 00:00:00 2001
From: Ralf Hemmecke <[email protected]>
Date: Thu, 12 Dec 2019 22:49:23 +0100
Subject: bugfix representation optimization of IntegerMod
Before the patch, SingleInteger was also choosen as representation
for IntegerMod(p) if p was in the range m/2 < p <= m := max()$SingleInteger.
(1) -> I ==> SingleInteger
(2) -> p: I := max()$I - 123456
(2) 4611686018427264447
Type: SingleInteger
(3) -> a: I := p - 1
(3) 4611686018427264446
Type: SingleInteger
(4) -> a + a
>> System error:
The value
9223372036854528892
is not of type
FIXNUM
(4) -> addmod(a, a, p)
>> System error:
The value
9223372036854528892
is not of type
FIXNUM
---
src/algebra/fmod.spad | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/src/algebra/fmod.spad b/src/algebra/fmod.spad
index a0490b3a..efc75dad 100644
--- a/src/algebra/fmod.spad
+++ b/src/algebra/fmod.spad
@@ -17,7 +17,7 @@ IntegerMod(p : PositiveInteger):
lookup x == (zero? x => p; (convert(x)@Integer) :: PositiveInteger)
-- Code is duplicated for the optimizer to kick in.
- if p <= convert(max()$SingleInteger)@Integer then
+ if p <= convert(shift(max()$SingleInteger, -1))@Integer then
Rep := SingleInteger
q := p::SingleInteger
--
2.17.1
