User talk:Wherrera: Difference between revisions
m
no edit summary
No edit summary |
mNo edit summary |
||
| (11 intermediate revisions by 5 users not shown) | |||
Line 13:
Yes, I found out how to do it in CoffeeScript. But Nim will be harder as it lacks run time eval. eval is available only for compile time. I think it should be possible to enter new molecules without having to recompile. So, I guess, an interpreted language is needed.
Also, regexes seem to have very different apis between languages. They seem to be as quick as handwritten parsing, though. --[[User:ChristerNilsson|ChristerNilsson]] ([[User talk:ChristerNilsson|talk]]) 01:24, 20 March 2019 (UTC)
== Your example for [http://rosettacode.org/wiki/Palindromic_gapful_numbers#Julia Palindromic gapful numbers] ==
has wrong output for 1,000,000 for digit 9.Maybe there is an Int64 overflow 91,189,796,469,798,119 = 9.1E16 [[User:Horst.h|Horst.h]] ([[User talk:Horst.h|talk]]) 10:39, 15 November 2019 (UTC)
There should not be an overflow with 64 bit integers and those numbers. It may be a variation in generation order between implementations.
-- [[User:Wherrera|Wherrera]] 19:02, 15 November 2019 (UTC)
Found the problem: I had a floating point precision error. Thanks for checking.
-- [[User:Wherrera|Wherrera]] 23:54, 15 November 2019 (UTC)
== comments about source statements that can start in column one ==
Concerning the Rosetta Code task (''Long literals, with continuations'') regarding (source) statements that can start in column other then one was meant for those computer programming languages that have column dependencies, some of which are (or used to be) such languages like:
:* BASIC (various flavors) some columns were meant for statement numbers
:* COBOL
:* older versions/flavors of FORTRAN (note the uppercase spelling) when columns 1 --> 5 were meant for statement numbers, and column 6 was for continuation), nowadays, it seems that most Fortrans are free-form
:* PL/I (used to) optionally reserve column one for carriage control, and statements started in column two
:* some assembler languages, where tokens starting in column one were reserved for statement labels
:* other computer languages that used a non-blank character in column seventy-two for continuation
:* other computer languages that used columns 73 --> 80 for sequencing numbers
:* ... and I'm sure many other (possibly older if not ancient) languages had column specifications for (statement) start and/or continuation
It would be interesting to learn (and know of) these old restrictions/specifications for non-free form computer programming languages. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 05:28, 24 March 2020 (UTC)
Fixed line formats and continuation columns made good sense when programs came in decks of punch cards, and not really much since.--[[User:Wherrera|Wherrera]] ([[User talk:Wherrera|talk]]) 07:41, 24 March 2020 (UTC)
: I wholeheartedly agree. I don't know which modern computer programming languages (other than a few) that still have restrictions (or rules) regarding fixed line formats and/or continuation columns, and there are still (machine) assemblers still being used, and I have no idea how many of them have columnar restrictions. I believe '''COBOL''' still has such restrictions, albeit even though it has object-oriented features, I don't know if it is considered modern because of the ancient lineage. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 14:40, 24 March 2020 (UTC)
== Intentional task demotion? ==
Did you mean to remove [[Bioinformatics/Global alignment]] and [[Doomsday rule]] as tasks? I see you removed the task markup, so they are no longer listed as tasks, and that is throwing off statistical calculations in the reports I generate. (Phix and Wren have over 100% completion.). I rather suspect that you meant to remove the '''draft''' part of the markup rather than the '''task''' part. I am provisionally going to re-add that. --[[User:Thundergnat|Thundergnat]] ([[User talk:Thundergnat|talk]]) 11:06, 31 October 2022 (UTC)
:: :: No this was supposed to change from draft status to regular task -- i did not know that had happened! So, the "task" label is always needed! I will try to not just remove the draft without adding the 'task' label then. --[[User:Wherrera|Wherrera]] ([[User talk:Wherrera|talk]]) 18:19, 31 October 2022 (UTC)
== Speed of your non-recursive Legendre prime counting function in Julia... ==
I ran your contribution on my machine to see how it compared to other language versions I had contributed, to find your translation of Nim is quite slow for the following reasons:
# The type of the argument counting function is the generic "::Integer" abstract type, which means that whatever type comes in will be the type of all the integers within the function (default ::Int64 on a 64-bit machine).
# You didn't keep the optimization of doing the division using floating point, which while not as fast in Julia as in Nim due to the speed of the conversion, does make a difference. While it is true that the precision of using floating point divisions means that counts to ranges over about 0.9e16 won't be accurate, this is a very high range for this algorithm due to high memory use and that alternate algorithms use much less memory and and a little faster.
# you are using even more memory because all of the arrays are this default size, meaning that "smalls" and "roughs" which only need to be 32-bits for a 64-bit argument (this algorithm is too slow and takes too much memory, even with these suggested improvement, to use anywhere near the 64-bit limit let alone for higher ranges), so the algorithm as you wrote it will be using about twice as much memory as the Nim version: 1.6 Gigabytes counting to 1e16 rather than 0.9 Gigabytes.
I fixed the above problems in the following Julia code, but didn't want to submit it myself as Julia isn't one of my commonly used languages and I might have missed something:
<syntaxhighlight lang="julia">function countprimes(n::UInt64)
n < 3 && return typeof(n)(n > 1)
@inline half(i::Integer) = (i - 1) >> 1
@inline divide(nm::Integer, d::Integer) = Integer(trunc(Float64(nm) / Float64(d)))
rtlmt = isqrt(n)
mxndx = (rtlmt - 1) ÷ 2
smalls::Array{UInt32} = [i for i in 0:mxndx+1]
roughs::Array{UInt32} = [i + i + 1 for i in 0:mxndx+1]
larges::Array{Int64} = [(n ÷ (i + i + 1) - 1) ÷ 2 for i in 0:mxndx+1]
cmpsts = falses(mxndx + 1)
bp, npc, mxri = 3, 0, mxndx
while true
i = bp >> 1
sqri = (i + i) * (i + 1)
sqri > mxndx && break
if !cmpsts[i + 1]
cmpsts[i + 1] = true
for c in sqri:bp:mxndx
cmpsts[c + 1] = true
end
ri = 0
for k in 0:mxri
q = roughs[k + 1]
qi = q >> 1
cmpsts[qi + 1] && continue
d = UInt64(bp) * UInt64(q)
larges[ri + 1] = larges[k + 1] + npc -
(d <= rtlmt ? larges[smalls[d >> 1 + 1] - npc + 1]
: smalls[half(divide(n, d)) + 1])
roughs[ri + 1] = q
ri += 1
end
m = mxndx
for k in (rtlmt ÷ bp - 1) | 1 : -2 : bp
c = smalls[k >> 1 + 1] - npc
ee = (k * bp) >> 1
while m >= ee
smalls[m + 1] -= c
m -= 1
end
end
mxri = ri - 1
npc += 1
end
bp += 2
end
result = larges[1]
for i in 2:mxri+1
result -= larges[i]
end
result += (mxri + 1 + 2 * (npc - 1)) * mxri ÷ 2
for j in 1:mxri
p = UInt64(roughs[j + 1])
m = n ÷ p
ee = smalls[half(m ÷ p) + 1] - npc
ee <= j && break
for k in j+1:ee
result += smalls[half(divide(m, UInt64(roughs[k + 1]))) + 1]
end
result -= (ee - j) * (npc + j - 1)
end
return result + 1
end
@time(println("π(10^9) = ", countprimes(UInt64(10)^9)))
@time(for i in 0:14
println("π(10^$i) = ", countprimes(UInt64(10)^i))
end)</syntaxhighlight>
Unless I am missing something, the above code takes about ten seconds on my machine and about three minutes to count to 1e16 (incorrectly as noted due to precision problems), which makes it about the speed of my JavaScript contribution of the same algorithm and slower than my Kotlin and F# contributions as well as most other native code compiling languages, which you might want to look into to see if something more can be done. --[[User:GordonBGood|GordonBGood]] ([[User talk:GordonBGood|talk]]) 03:33, 12 November 2022 (UTC)
That is right. I see no speedup with your corrections, so I think that the problem may lie elsewhere. --[[User:Wherrera|Wherrera]] ([[User talk:Wherrera|talk]]) 05:58, 12 November 2022 (UTC)
It looks as if using the precalculated values from Nim example speeds it by about 20%. I suspect more can be wrung out. --[[User:Wherrera|Wherrera]] ([[User talk:Wherrera|talk]]) 21:22, 12 November 2022 (UTC)
| |||