-
Notifications
You must be signed in to change notification settings - Fork 136
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
gcd_ crashes for zero $-variables #191
Comments
Output of
Output of
|
I think
Output:
Should we not expect If the polynomial has only 1 term the result seems fine.
Output:
|
Actually Valgrind tells us something goes wrong at ratio.c:2063 in these cases, too:
|
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 ***@***.***> 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 <#191 (comment)>, 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
|
It seems that mathematically it makes sense or at least there is some convention. Mathematica 11.0.1
Python 3.6.1
ginsh 1.7.2
gp/pari 2.9.2
If |
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 ***@***.***> 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 <#191 (comment)>, 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 That |
After applying the patch 615cbcd, still broken...
|
I found cases that are still broken...
|
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:
The text was updated successfully, but these errors were encountered: