October 2020

tgan · 2020-10-01, 11:32

https://www.research.ibm.com/haifa/p...tober2020.html

This one looks complicated

uau · 2020-10-01, 13:28

The control graph example image at the end ("Here's a sample program, along with its control-flow graph:") doesn't seem to load.

SmartMersenne · 2020-10-01, 18:46

The question is also ill-posed, needs many clarifications. For example: how does the algorithm will work for negative integers? Return value of modulo operation changes from one programming language to another.

SmartMersenne · 2020-10-01, 19:57

Here are the different results of modulo operation for negative numbers in some commonly known languages:

https://torstencurdt.com/tech/posts/...ative-numbers/

Citrix · 2020-10-02, 05:47

Possible hint if I understand the question correctly (I agree that the language is not very clear).

Hint: https://cs.stackexchange.com/questions/63572/what-is-the-mathcal-o-of-subtraction-based-gcd-algorithm

Dieter · 2020-10-05, 08:13

Can anyone explain to me
- why the ** in "**20** lines"?
- why the $ in "length $n$"?
- which other path than 10-20-30-40-70-90 is possible in the sample program?
- what will say "the number of paths ... is the sequence 0,2,2,...?" Isn't the number dependent of a,b? Does 0 make sense?
Perhaps I'm the only one who doesn't understand this.

SmartMersenne · 2020-10-05, 09:40

Quote:

Originally Posted by Dieter

Can anyone explain to me
- why the ** in "**20** lines"?
- why the $ in "length $n$"?
- which other path than 10-20-30-40-70-90 is possible in the sample program?
- what will say "the number of paths ... is the sequence 0,2,2,...?" Isn't the number dependent of a,b? Does 0 make sense?
Perhaps I'm the only one who doesn't understand this.

Trust me, you are not the only one.

I think ** and $ is just for formatting, and you can ignore.

The sample program is not an indicator of what to expect from the real problem, let alone the missing image is not helping at all.

virgo · 2020-10-05, 09:47

Its similar to assembly codes

I think its about how to make jump below( jump condition on a>b or a<b) logic within 20lines
btw I still dont know why they added chaos operator

Dieter · 2020-10-05, 10:17

It's no problem to write a code with 20 lines (not using "chaos lines", of course) for the search of the gcd, if I take a>b>0 for granted, and to draw the control-flow graph. But the paths are dependent of a and b, and so I don't know how to achieve the given sequence. And the zero!

uau · 2020-10-05, 19:22

I interpreted it as creating the control-flow graph based only on the existence of jump commands, so it does not depend on values of a and b. Actual behavior of the program will depend on those, but the graph won't.

I believe the sequence 0, 2, 2, ... starts from 1 for path length (that's another kind-of-flaw in the problem description, as it links to an OEIS sequence with a definition that doesn't match, without mentioning that you need a different offset). The 0 means that there is no direct path from the starting node in the graph to the end node, then 2 means there are 2 possible paths with 2 steps.

Dieter · 2020-10-05, 20:56

Quote:

Originally Posted by uau

I interpreted it as creating the control-flow graph based only on the existence of jump commands, so it does not depend on values of a and b. Actual behavior of the program will depend on those, but the graph won't.

I believe the sequence 0, 2, 2, ... starts from 1 for path length (that's another kind-of-flaw in the problem description, as it links to an OEIS sequence with a definition that doesn't match, without mentioning that you need a different offset). The 0 means that there is no direct path from the starting node in the graph to the end node, then 2 means there are 2 possible paths with 2 steps.

Thank you. Good explanation. The length of a path from the entry node to the exit node is the number of needed edges. a6 = 17 will say that there are 17 different paths from entry to exit needing 6 edges.
Meanwhile the cfg of the example can be seen, and it were a good exercise to write down the sequence:
0,0,0,1,... (there is no path of length 1,2,3 and only one path of length 4)
Unfortunately I don't understand the edge from 60 to 70.

2020-10-01, 11:32	#1
tgan Jul 2015 5² Posts	October 2020 https://www.research.ibm.com/haifa/p...tober2020.html This one looks complicated

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
October 2019	Xyzzy	Puzzles	21	2019-11-07 13:13
October 2016	R. Gerbicz	Puzzles	10	2016-11-01 13:35
October 2015	LaurV	Puzzles	3	2015-11-02 15:22
October 2014	Xyzzy	Puzzles	8	2014-11-02 19:03
13 October is approaching!	Joe O	Prime Sierpinski Project	1	2010-10-09 06:12

2020-10-01, 13:28	#2
uau Jan 2017 2³·11 Posts	The control graph example image at the end ("Here's a sample program, along with its control-flow graph:") doesn't seem to load.

2020-10-01, 18:46	#3
SmartMersenne Sep 2017 143₈ Posts	The question is also ill-posed, needs many clarifications. For example: how does the algorithm will work for negative integers? Return value of modulo operation changes from one programming language to another.

2020-10-01, 19:57	#4
SmartMersenne Sep 2017 3²×11 Posts	Here are the different results of modulo operation for negative numbers in some commonly known languages: https://torstencurdt.com/tech/posts/...ative-numbers/

2020-10-02, 05:47	#5
Citrix Jun 2003 1,579 Posts	Possible hint if I understand the question correctly (I agree that the language is not very clear). Hint: https://cs.stackexchange.com/questions/63572/what-is-the-mathcal-o-of-subtraction-based-gcd-algorithm

2020-10-05, 08:13	#6
Dieter Oct 2017 1101110₂ Posts	Can anyone explain to me - why the in "20** lines"? - why the $ in "length $n$"? - which other path than 10-20-30-40-70-90 is possible in the sample program? - what will say "the number of paths ... is the sequence 0,2,2,...?" Isn't the number dependent of a,b? Does 0 make sense? Perhaps I'm the only one who doesn't understand this.

2020-10-05, 09:47	#8
virgo Apr 2020 5 Posts	Its similar to assembly codes I think its about how to make jump below( jump condition on a>b or a<b) logic within 20lines btw I still dont know why they added chaos operator

2020-10-05, 10:17	#9
Dieter Oct 2017 2·5·11 Posts	It's no problem to write a code with 20 lines (not using "chaos lines", of course) for the search of the gcd, if I take a>b>0 for granted, and to draw the control-flow graph. But the paths are dependent of a and b, and so I don't know how to achieve the given sequence. And the zero!

2020-10-05, 19:22	#10
uau Jan 2017 1011000₂ Posts	I interpreted it as creating the control-flow graph based only on the existence of jump commands, so it does not depend on values of a and b. Actual behavior of the program will depend on those, but the graph won't. I believe the sequence 0, 2, 2, ... starts from 1 for path length (that's another kind-of-flaw in the problem description, as it links to an OEIS sequence with a definition that doesn't match, without mentioning that you need a different offset). The 0 means that there is no direct path from the starting node in the graph to the end node, then 2 means there are 2 possible paths with 2 steps.