Closed tueda closed 7 years ago
gcd_
also crashes occasionally on mac os x (though not on my linux machine) when a zero expression is in the first argument.
Input:
#-
off statistics;
L p1 = 0;
L p2 = 1;
#do i = 1,100000
*L gcd = gcd_(p2,p1); * Works
L gcd = gcd_(p1,p2); * Fails
.sort
#enddo
.end
Output of form
(on mac):
FORM 4.1 (Jun 6 2017, v4.1-20131025-347-g76561be) 64-bits Run: Wed Jun 7 00:07:13 2017
#-
Program terminating at bug.frm Line 7 -->
0.00 sec out of 0.00 sec
Output of tform
(on mac):
TFORM 4.1 (Jun 6 2017, v4.1-20131025-347-g76561be) 64-bits 0 workers Run: Wed Jun 7 00:14:06 2017
#-
Term too complex during normalization
Called from GCDfunction
Program terminating in thread 0 at bug.frm Line 7 -->
tform(4759,0x7fff774eb000) malloc: *** error for object 0x7fe370d00250: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
Abort trap: 6
I think gcd_
also gives wrong results when called with a zero.
Input:
#-
off statistics;
S x;
L p1 = 0;
L p2 = x+x^2;
L gcd = gcd_(p2,p1);
print;
.end
Output:
TFORM 4.1 (Jun 6 2017, v4.1-20131025-347-g76561be) 64-bits 0 workers Run: Wed Jun 7 00:17:22 2017
#-
p1 = 0;
p2 =
x + x^2;
gcd =
1;
Should we not expect gcd = x+x^2
?
If the polynomial has only 1 term the result seems fine. Input:
#-
off statistics;
S x;
L p1 = 0;
L p2 = x^2;
L gcd = gcd_(p2,p1);
print;
.end
Output:
FORM 4.1 (Jun 6 2017, v4.1-20131025-347-g76561be) 64-bits Run: Wed Jun 7 00:19:24 2017
#-
p1 = 0;
p2 =
x^2;
gcd =
x^2;
gcd_
also crashes occasionally on mac os x (though not on my linux machine) when a zero expression is in the first argument.I think
gcd_
also gives wrong results when called with a zero.
Actually Valgrind tells us something goes wrong at ratio.c:2063 in these cases, too:
FORM 4.1 (Jun 6 2017, v4.1-20131025-347-g76561be) 64-bits Run: Wed Jun 7 00:49:52 2017
L p1 = 0;
L p2 = 1;
L gcd = gcd_(p1,p2);
.end
Time = 0.06 sec Generated terms = 0
p1 Terms in output = 0
Bytes used = 4
Time = 0.08 sec Generated terms = 1
p2 Terms in output = 1
Bytes used = 20
==23356== Invalid read of size 4
==23356== at 0x4BFDDD: GCDterms (ratio.c:2063)
==23356== by 0x4C1518: GCDfunction (ratio.c:1000)
==23356== by 0x4B7725: Generator (proces.c:3688)
==23356== by 0x4B7C7A: Generator (proces.c:3886)
==23356== by 0x4B93FA: Processor (proces.c:404)
==23356== by 0x437480: DoExecute (execute.c:812)
==23356== by 0x44D8FE: ExecModule (module.c:274)
==23356== by 0x4AF44B: PreProcessor (pre.c:962)
==23356== by 0x4E7A30: main (startup.c:1605)
==23356== Address 0x570977c is 4 bytes before a block of size 96 alloc'd
==23356== at 0x4A05A57: malloc (vg_replace_malloc.c:299)
==23356== by 0x4FE510: Malloc1 (tools.c:2236)
==23356== by 0x4E230B: EndSort (sort.c:741)
==23356== by 0x4BFD85: CreateExpression (ratio.c:2037)
==23356== by 0x4C141C: GCDfunction (ratio.c:977)
==23356== by 0x4B7725: Generator (proces.c:3688)
==23356== by 0x4B7C7A: Generator (proces.c:3886)
==23356== by 0x4B93FA: Processor (proces.c:404)
==23356== by 0x437480: DoExecute (execute.c:812)
==23356== by 0x44D8FE: ExecModule (module.c:274)
==23356== by 0x4AF44B: PreProcessor (pre.c:962)
==23356== by 0x4E7A30: main (startup.c:1605)
==23356==
==23356== Invalid read of size 4
==23356== at 0x4C0392: GCDterms (ratio.c:2224)
==23356== by 0x4C1518: GCDfunction (ratio.c:1000)
==23356== by 0x4B7725: Generator (proces.c:3688)
==23356== by 0x4B7C7A: Generator (proces.c:3886)
==23356== by 0x4B93FA: Processor (proces.c:404)
==23356== by 0x437480: DoExecute (execute.c:812)
==23356== by 0x44D8FE: ExecModule (module.c:274)
==23356== by 0x4AF44B: PreProcessor (pre.c:962)
==23356== by 0x4E7A30: main (startup.c:1605)
==23356== Address 0x570977c is 4 bytes before a block of size 96 alloc'd
==23356== at 0x4A05A57: malloc (vg_replace_malloc.c:299)
==23356== by 0x4FE510: Malloc1 (tools.c:2236)
==23356== by 0x4E230B: EndSort (sort.c:741)
==23356== by 0x4BFD85: CreateExpression (ratio.c:2037)
==23356== by 0x4C141C: GCDfunction (ratio.c:977)
==23356== by 0x4B7725: Generator (proces.c:3688)
==23356== by 0x4B7C7A: Generator (proces.c:3886)
==23356== by 0x4B93FA: Processor (proces.c:404)
==23356== by 0x437480: DoExecute (execute.c:812)
==23356== by 0x44D8FE: ExecModule (module.c:274)
==23356== by 0x4AF44B: PreProcessor (pre.c:962)
==23356== by 0x4E7A30: main (startup.c:1605)
==23356==
Time = 0.09 sec Generated terms = 1
gcd Terms in output = 1
Bytes used = 20
FORM 4.1 (Jun 6 2017, v4.1-20131025-347-g76561be) 64-bits Run: Wed Jun 7 00:51:07 2017
S x;
L p1 = 0;
L p2 = x+x^2;
L gcd = gcd_(p2,p1);
.end
Time = 0.06 sec Generated terms = 0
p1 Terms in output = 0
Bytes used = 4
Time = 0.08 sec Generated terms = 2
p2 Terms in output = 2
Bytes used = 60
==23416== Invalid read of size 4
==23416== at 0x4BFDDD: GCDterms (ratio.c:2063)
==23416== by 0x4C1518: GCDfunction (ratio.c:1000)
==23416== by 0x4B7725: Generator (proces.c:3688)
==23416== by 0x4B7C7A: Generator (proces.c:3886)
==23416== by 0x4B93FA: Processor (proces.c:404)
==23416== by 0x437480: DoExecute (execute.c:812)
==23416== by 0x44D8FE: ExecModule (module.c:274)
==23416== by 0x4AF44B: PreProcessor (pre.c:962)
==23416== by 0x4E7A30: main (startup.c:1605)
==23416== Address 0x1c9a566c is 4 bytes before a block of size 96 alloc'd
==23416== at 0x4A05A57: malloc (vg_replace_malloc.c:299)
==23416== by 0x4FE510: Malloc1 (tools.c:2236)
==23416== by 0x4E230B: EndSort (sort.c:741)
==23416== by 0x4BFD85: CreateExpression (ratio.c:2037)
==23416== by 0x4C141C: GCDfunction (ratio.c:977)
==23416== by 0x4B7725: Generator (proces.c:3688)
==23416== by 0x4B7C7A: Generator (proces.c:3886)
==23416== by 0x4B93FA: Processor (proces.c:404)
==23416== by 0x437480: DoExecute (execute.c:812)
==23416== by 0x44D8FE: ExecModule (module.c:274)
==23416== by 0x4AF44B: PreProcessor (pre.c:962)
==23416== by 0x4E7A30: main (startup.c:1605)
==23416==
==23416== Invalid read of size 4
==23416== at 0x4C0392: GCDterms (ratio.c:2224)
==23416== by 0x4C1518: GCDfunction (ratio.c:1000)
==23416== by 0x4B7725: Generator (proces.c:3688)
==23416== by 0x4B7C7A: Generator (proces.c:3886)
==23416== by 0x4B93FA: Processor (proces.c:404)
==23416== by 0x437480: DoExecute (execute.c:812)
==23416== by 0x44D8FE: ExecModule (module.c:274)
==23416== by 0x4AF44B: PreProcessor (pre.c:962)
==23416== by 0x4E7A30: main (startup.c:1605)
==23416== Address 0x1c9a566c is 4 bytes before a block of size 96 alloc'd
==23416== at 0x4A05A57: malloc (vg_replace_malloc.c:299)
==23416== by 0x4FE510: Malloc1 (tools.c:2236)
==23416== by 0x4E230B: EndSort (sort.c:741)
==23416== by 0x4BFD85: CreateExpression (ratio.c:2037)
==23416== by 0x4C141C: GCDfunction (ratio.c:977)
==23416== by 0x4B7725: Generator (proces.c:3688)
==23416== by 0x4B7C7A: Generator (proces.c:3886)
==23416== by 0x4B93FA: Processor (proces.c:404)
==23416== by 0x437480: DoExecute (execute.c:812)
==23416== by 0x44D8FE: ExecModule (module.c:274)
==23416== by 0x4AF44B: PreProcessor (pre.c:962)
==23416== by 0x4E7A30: main (startup.c:1605)
==23416==
Time = 0.10 sec Generated terms = 1
gcd Terms in output = 1
Bytes used = 20
OK, it is clear that the case that one of those arguments (or both) is zero is not intercepted. I guess there should be a runtime error, rather than a crash (or no crash but a nonsense answer). The gcd of 0 and any other number makes no sense. I will put some if statements in the code.
Jos
On 7 jun. 2017, at 01:01, Takahiro Ueda notifications@github.com wrote:
gcd_ also crashes occasionally on mac os x (though not on my linux machine) when a zero expression is in the first argument.
I think gcd_ also gives wrong results when called with a zero.
Actually Valgrind tells us something goes wrong at ratio.c:2063 https://github.com/vermaseren/form/blob/76561be553a6215cf4ef70c6d1a5b848bda7e12d/sources/ratio.c#L2063 in these cases, too:
FORM 4.1 (Jun 6 2017, v4.1-20131025-347-g76561be) 64-bits Run: Wed Jun 7 00:49:52 2017 L p1 = 0; L p2 = 1; L gcd = gcd_(p1,p2); .end
Time = 0.06 sec Generated terms = 0 p1 Terms in output = 0 Bytes used = 4
Time = 0.08 sec Generated terms = 1 p2 Terms in output = 1 Bytes used = 20 ==23356== Invalid read of size 4 ==23356== at 0x4BFDDD: GCDterms (ratio.c:2063) ==23356== by 0x4C1518: GCDfunction (ratio.c:1000) ==23356== by 0x4B7725: Generator (proces.c:3688) ==23356== by 0x4B7C7A: Generator (proces.c:3886) ==23356== by 0x4B93FA: Processor (proces.c:404) ==23356== by 0x437480: DoExecute (execute.c:812) ==23356== by 0x44D8FE: ExecModule (module.c:274) ==23356== by 0x4AF44B: PreProcessor (pre.c:962) ==23356== by 0x4E7A30: main (startup.c:1605) ==23356== Address 0x570977c is 4 bytes before a block of size 96 alloc'd ==23356== at 0x4A05A57: malloc (vg_replace_malloc.c:299) ==23356== by 0x4FE510: Malloc1 (tools.c:2236) ==23356== by 0x4E230B: EndSort (sort.c:741) ==23356== by 0x4BFD85: CreateExpression (ratio.c:2037) ==23356== by 0x4C141C: GCDfunction (ratio.c:977) ==23356== by 0x4B7725: Generator (proces.c:3688) ==23356== by 0x4B7C7A: Generator (proces.c:3886) ==23356== by 0x4B93FA: Processor (proces.c:404) ==23356== by 0x437480: DoExecute (execute.c:812) ==23356== by 0x44D8FE: ExecModule (module.c:274) ==23356== by 0x4AF44B: PreProcessor (pre.c:962) ==23356== by 0x4E7A30: main (startup.c:1605) ==23356== ==23356== Invalid read of size 4 ==23356== at 0x4C0392: GCDterms (ratio.c:2224) ==23356== by 0x4C1518: GCDfunction (ratio.c:1000) ==23356== by 0x4B7725: Generator (proces.c:3688) ==23356== by 0x4B7C7A: Generator (proces.c:3886) ==23356== by 0x4B93FA: Processor (proces.c:404) ==23356== by 0x437480: DoExecute (execute.c:812) ==23356== by 0x44D8FE: ExecModule (module.c:274) ==23356== by 0x4AF44B: PreProcessor (pre.c:962) ==23356== by 0x4E7A30: main (startup.c:1605) ==23356== Address 0x570977c is 4 bytes before a block of size 96 alloc'd ==23356== at 0x4A05A57: malloc (vg_replace_malloc.c:299) ==23356== by 0x4FE510: Malloc1 (tools.c:2236) ==23356== by 0x4E230B: EndSort (sort.c:741) ==23356== by 0x4BFD85: CreateExpression (ratio.c:2037) ==23356== by 0x4C141C: GCDfunction (ratio.c:977) ==23356== by 0x4B7725: Generator (proces.c:3688) ==23356== by 0x4B7C7A: Generator (proces.c:3886) ==23356== by 0x4B93FA: Processor (proces.c:404) ==23356== by 0x437480: DoExecute (execute.c:812) ==23356== by 0x44D8FE: ExecModule (module.c:274) ==23356== by 0x4AF44B: PreProcessor (pre.c:962) ==23356== by 0x4E7A30: main (startup.c:1605) ==23356==
Time = 0.09 sec Generated terms = 1 gcd Terms in output = 1 Bytes used = 20 FORM 4.1 (Jun 6 2017, v4.1-20131025-347-g76561be) 64-bits Run: Wed Jun 7 00:51:07 2017 S x; L p1 = 0; L p2 = x+x^2; L gcd = gcd_(p2,p1); .end
Time = 0.06 sec Generated terms = 0 p1 Terms in output = 0 Bytes used = 4
Time = 0.08 sec Generated terms = 2 p2 Terms in output = 2 Bytes used = 60 ==23416== Invalid read of size 4 ==23416== at 0x4BFDDD: GCDterms (ratio.c:2063) ==23416== by 0x4C1518: GCDfunction (ratio.c:1000) ==23416== by 0x4B7725: Generator (proces.c:3688) ==23416== by 0x4B7C7A: Generator (proces.c:3886) ==23416== by 0x4B93FA: Processor (proces.c:404) ==23416== by 0x437480: DoExecute (execute.c:812) ==23416== by 0x44D8FE: ExecModule (module.c:274) ==23416== by 0x4AF44B: PreProcessor (pre.c:962) ==23416== by 0x4E7A30: main (startup.c:1605) ==23416== Address 0x1c9a566c is 4 bytes before a block of size 96 alloc'd ==23416== at 0x4A05A57: malloc (vg_replace_malloc.c:299) ==23416== by 0x4FE510: Malloc1 (tools.c:2236) ==23416== by 0x4E230B: EndSort (sort.c:741) ==23416== by 0x4BFD85: CreateExpression (ratio.c:2037) ==23416== by 0x4C141C: GCDfunction (ratio.c:977) ==23416== by 0x4B7725: Generator (proces.c:3688) ==23416== by 0x4B7C7A: Generator (proces.c:3886) ==23416== by 0x4B93FA: Processor (proces.c:404) ==23416== by 0x437480: DoExecute (execute.c:812) ==23416== by 0x44D8FE: ExecModule (module.c:274) ==23416== by 0x4AF44B: PreProcessor (pre.c:962) ==23416== by 0x4E7A30: main (startup.c:1605) ==23416== ==23416== Invalid read of size 4 ==23416== at 0x4C0392: GCDterms (ratio.c:2224) ==23416== by 0x4C1518: GCDfunction (ratio.c:1000) ==23416== by 0x4B7725: Generator (proces.c:3688) ==23416== by 0x4B7C7A: Generator (proces.c:3886) ==23416== by 0x4B93FA: Processor (proces.c:404) ==23416== by 0x437480: DoExecute (execute.c:812) ==23416== by 0x44D8FE: ExecModule (module.c:274) ==23416== by 0x4AF44B: PreProcessor (pre.c:962) ==23416== by 0x4E7A30: main (startup.c:1605) ==23416== Address 0x1c9a566c is 4 bytes before a block of size 96 alloc'd ==23416== at 0x4A05A57: malloc (vg_replace_malloc.c:299) ==23416== by 0x4FE510: Malloc1 (tools.c:2236) ==23416== by 0x4E230B: EndSort (sort.c:741) ==23416== by 0x4BFD85: CreateExpression (ratio.c:2037) ==23416== by 0x4C141C: GCDfunction (ratio.c:977) ==23416== by 0x4B7725: Generator (proces.c:3688) ==23416== by 0x4B7C7A: Generator (proces.c:3886) ==23416== by 0x4B93FA: Processor (proces.c:404) ==23416== by 0x437480: DoExecute (execute.c:812) ==23416== by 0x44D8FE: ExecModule (module.c:274) ==23416== by 0x4AF44B: PreProcessor (pre.c:962) ==23416== by 0x4E7A30: main (startup.c:1605) ==23416==
Time = 0.10 sec Generated terms = 1 gcd Terms in output = 1 Bytes used = 20 — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/vermaseren/form/issues/191#issuecomment-306641540, or mute the thread https://github.com/notifications/unsubscribe-auth/AFLxEnd97VvDtRJRak78ca_pkoOeK0fgks5sBdpVgaJpZM4Nw_xX.
On Wed, 7 Jun 2017 at 8:11:12 -0700, Jos Vermaseren wrote:
The gcd of 0 and any other number makes no sense.
Unless I am misunderstanding I believe the proper definitions are
gcd(0,a) = a gcd(0,0) = 0
See page 3 of the book http://williamstein.org/books/ent/ent.pdf
The gcd of 0 and any other number makes no sense.
It seems that mathematically it makes sense or at least there is some convention.
Mathematica 11.0.1
In[1]:= PolynomialGCD[0, 1+x]
Out[1] = 1 + x
In[2]:= PolynomialGCD[0, 0]
Out[2] = 0
Python 3.6.1
In [1]: import math
In [2]: math.gcd(0, 12)
Out[2]: 12
In [3]: math.gcd(0, 0)
Out[2]: 0
ginsh 1.7.2
> gcd(0, 1+x);
1+x
> gcd(0, 0);
0
gp/pari 2.9.2
? gcd(0, 1+x)
%1 = x + 1
? gcd(0, 0)
%2 = 0
GCD(0,0) = 0
would be true in mathematics, e.g., https://math.stackexchange.com/questions/495119/what-is-gcd0-0, but in practice I'm happy with the fact that FORM gives a wrong answer for gcd_(0,0) -> 1
because usually what we want to do after taking a GCD is dividing by the GCD:
$gcd = gcd_($a,$b);
$a = div_($a,$gcd);
$b = div_($b,$gcd);
If gcd_(0,0)
gives 0, I need to put more code to check if the GCD is 0 before the divisions.
If I look in the book, it is more like a definition or convention. Specially when both are 0. If you have gcd(0,x) can you say that x divides zero? At the least that is very shady. I can make it like the ‘convention’ of course. It is not very elegant in my eyes, but if it is what people want…..
Jos
On 7 jun. 2017, at 17:28, Takahiro Ueda notifications@github.com wrote:
The gcd of 0 and any other number makes no sense.
It seems that mathematically it makes sense or at least there is some convention.
Mathematica 11.0.1
In[1]:= PolynomialGCD[0, 1+x]
Out[1] = 1 + x
In[2]:= PolynomialGCD[0, 0]
Out[2] = 0 Python 3.6.1
In [1]: import math
In [2]: math.gcd(0, 12) Out[2]: 12
In [3]: math.gcd(0, 0) Out[2]: 0 ginsh 1.7.2
gcd(0, 1+x); 1+x gcd(0, 0); 0 gp/pari 2.9.2
? gcd(0, 1+x) %1 = x + 1 ? gcd(0, 0) %2 = 0 GCD(0,0) = 0 would be true in mathematics, e.g., https://math.stackexchange.com/questions/495119/what-is-gcd0-0 https://math.stackexchange.com/questions/495119/what-is-gcd0-0, but in practice I'm happy with the fact that FORM gives the "wrong" answer for gcd_(0,0) -> 1 because usually what we want to do after taking a GCD is divisions by the GCD:
$gcd = gcd($a,$b); $a = div($a,$gcd); $b = div($b,$gcd); If gcd(0,0) gives 0, I need to put more code to check if the GCD is 0 before the divisions.
— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/vermaseren/form/issues/191#issuecomment-306831034, or mute the thread https://github.com/notifications/unsubscribe-auth/AFLxEsPDBWxDlg6wGuFYajmEsnYdVuB3ks5sBsGMgaJpZM4Nw_xX.
On Wed, 7 Jun 2017 at 9:21:38 -0700, Jos Vermaseren wrote:
If you have gcd(0,x) can you say that x divides zero?
Yes, for 0/x = 0 is well defined.
At the least that is very shady. I can make it like the ‘convention’ of course. It is not very elegant in my eyes, but if it is what people want…..
I don't think one can "define" gcd(0,x) any differently than 'x' because one of the properties of the gcd() would be violated otherwise, namely
gcd(a,b) = gcd(a,b-a).
The above lemma would be inconsistent with gcd(a,a) = a unless gcd(a,0) = a.
I believe @tueda and @crmafra are correct that gcd(0,a)=a
when a !=0
. This follows from 0/a=0
(i.e... a
is a divisor of 0
) this is not a convention.
That gcd(0,0)=0
is a (popular) convention. Perhaps this is convenient for polynomial gcd since we can compute gcd(0,a)=a
with general a
then set a=0
consistently.
After applying the patch 615cbcd52634, still broken...
FORM 4.1 (Jun 8 2017, v4.1-20131025-348-g615cbcd) 64-bits Run: Thu Jun 8 14:59:51 2017
S x;
#$a = 0;
#$b = 1+x;
#$c = gcd_($a,$b);
==28608== Invalid read of size 4
==28608== at 0x4BFDDD: GCDterms (ratio.c:2073)
==28608== by 0x4C0519: GCDfunction3 (ratio.c:1146)
==28608== by 0x4C1850: GCDfunction (ratio.c:1051)
==28608== by 0x4B7725: Generator (proces.c:3688)
==28608== by 0x42E4CE: CatchDollar (dollar.c:112)
==28608== by 0x4AF710: PreProcessor (pre.c:1050)
==28608== by 0x4E7B4B: main (startup.c:1605)
==28608== Address 0x57094cc is 4 bytes before a block of size 8 alloc'd
==28608== at 0x4A05A57: malloc (vg_replace_malloc.c:299)
==28608== by 0x4FE62B: Malloc1 (tools.c:2236)
==28608== by 0x4C04E6: GCDfunction3 (ratio.c:1142)
==28608== by 0x4C1850: GCDfunction (ratio.c:1051)
==28608== by 0x4B7725: Generator (proces.c:3688)
==28608== by 0x42E4CE: CatchDollar (dollar.c:112)
==28608== by 0x4AF710: PreProcessor (pre.c:1050)
==28608== by 0x4E7B4B: main (startup.c:1605)
... (many errors) ...
I found cases that are still broken...
FORM 4.1 (Jun 8 2017, v4.1-20131025-351-g31c5798) 64-bits Run: Thu Jun 8 22:13:09 2017
S x;
L F1 = gcd_(100000000000000000000,0);
L F2 = gcd_(-x,0);
P;
.end
Time = 0.00 sec Generated terms = 0
F1 Terms in output = 0
Bytes used = 4
Time = 0.00 sec Generated terms = 0
F2 Terms in output = 0
Bytes used = 4
F1 = 0;
F2 = 0;
It seems that 7cf7c42df5b6fb97 finally fixes bugs for gcd_(0,0)
, gcd_(a,0)
and gcd_(0,a)
. I close this issue. (But still we have #196.)
Thanks a lot for quickly fixing this. With 541f847 on Mac everything runs as expected.
gcd_
has a memory bug when the first argument is a zero $-variable.Valgrind output: