Anonymous user
Talk:Zig-zag matrix: Difference between revisions
→Pattern of memory addresses: Previous pattern searches.
(The first N squared integers) |
(→Pattern of memory addresses: Previous pattern searches.) |
||
| (14 intermediate revisions by 4 users not shown) | |||
Line 418:
Thanks for the info! I've updated the Haskell example with a better algorithm based on your techniques. (By the way, I think this explanation is worth keeping around; perhaps it should be moved to something like [[Zig Zag/J explanation]] and linked from the example?) --[[User:Kevin Reid|Kevin Reid]] 17:49, 4 August 2008 (UTC)
:I took the fact that you sorted in the
Even though J looks so strange and hard to me, this algo so explained and encoded gave me the idea that J deserves a look and more:) --[[User:ShinTakezou|ShinTakezou]] 01:00, 16 December 2008 (UTC)
Line 432:
== The first N squared integers ==
Integers start at minus a very big number. So this is not what the task description means. Positive integers start at 1, this would be my preferred requirement, but many already start at zero which is neither positive nor negative. The task description needs correction.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 13:55, 24 January 2020 (UTC)
: I agree wholeheartedly. Or, as one often votes on Rosetta Code, '''+1'''. I also have brought up more than a few similar arguments before, as in ''' ''a positive integer > 0'',''' or ''' ''a positive integer'',''' and then use a '''0''' (zero) in the example input for the task. It's an uphill battle, not the least of which is when a '''number''' is used when an '''integer''' is meant. I have since stopped pointing out the obvious, ya can't win when ya argue with people who buy ink by the barrel. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 20:46, 24 January 2020 (UTC)
:It is an old task with many solutions; maybe rewording to include a start of zero ''or'' one would be better as the main idea of the task is the zig-zaggedness and starting from one or zero would still allow implementations to be compared? --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 21:21, 24 January 2020 (UTC)
::Hmm, just saw that the example counts from zero. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 21:26, 24 January 2020 (UTC)
:: I addressed this problem when I entered the '''REXX''' language solution, the computer program allowed the invoker to specify a starting ''number'', but any integer could be used. It doesn't fix the problem with the task's requirements, but it allows the user to choose which integer to start the zig-zag matrix with. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 21:39, 24 January 2020 (UTC)
: The problem with using phrases like ''natural numbers'' and/or ''counting numbers'' is that there isn't a clear and agreed-upon definition(s), some include zero, others do not. The same problem exists with ''whole numbers''. Note that Wikipedia says that in computer science, ''natural numbers'' always includes zero. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 21:42, 24 January 2020 (UTC)
== what is the first natural number? ==
So the question is now, what is the first ''natural number''? -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 21:52, 24 January 2020 (UTC)
:If we allow zero or one to ''both'' be allowed then it could mean minimal rework of examples whilst hopefully retaining the spirit of the old task?
:(I am a little biased, as this is one of the existing tasks that first attracted me to RC - I based the second task I started, "Spiral matrix", on this one and have fond memories).
:--[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 09:20, 25 January 2020 (UTC)
== Pattern of memory addresses ==
If we assume that each entry is stored consecutively in memory like so (using size 5 as an example), and assuming an 8-bit computer where each memory address holds a byte and each address is 16-bit
<pre>;these are memory locations, the values within are as in the example.
$1200 $1201 $1202 $1203 $1204
$1205 $1206 $1207 $1208 $1209
$120A $120B $120C $120D $120E
$120F $1210 $1211 $1212 $1213
$1214 $1215 $1216 $1217 $1218
</pre>
Then to get to the next memory address, we add the following numbers to the one we're at.
Let N = the size of the array and K = N-1. Then:
<pre>
$1200 + 1 = $1201
$1201 + K = $1205
$1205 + N = $120A
$120A - K = $1206
$1206 - K = $1202
$1202 + 1 = $1203
$1203 + K = $1207
$1207 + K = $120B
$120B + K = $120F
$120F + N = $1214
$1214 - K = $1210
$1210 - K = $120C
$120C - K = $1208
$1208 - K = $1204
$1204 + N = $1209
$1209 + K = $120D
$120D + K = $1211
$1211 + K = $1215
$1215 + 1 = $1216
$1216 - K = $1212
$1212 - K = $120E
$120E + N = $1213
$1217 + 1 = $1218
</pre>
It seems to follow this pattern:
<pre> +1, +K, +N, -2K, +1, +3K, +N, -(K^2), +1, +N, +3K, +1, -2K, +N, +K, +1</pre>
I tried it again with a N=4 and got this sequence:
<pre> +1, +K, +N, -2K, +1, +(K^2), +1, -2K, +N, +K, +1</pre>
If you remove the <math>k^2</math> and +1 after it, the sequence is symmetric.
Might be helpful for establishing a pattern. I'll work on it more later. This logic should extend to 32-bit CPUs if you multiply N and K by 4.--[[User:Puppydrum64|Puppydrum64]] ([[User talk:Puppydrum64|talk]]) 17:06, 15 September 2021 (UTC)
:Hi Puppydrum64; at the top of the talk page the author of the J example talks about his solution that exploits patterns in indices. I just noticed that sort was involved and worked out something for the Python entry and explained it in my blog: [http://paddy3118.blogspot.com/2008/08/zig-zag.html paddy3118 blog explanation].
: There ''are'' patterns to be found :-)
: --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 07:44, 18 September 2021 (UTC)
| |||