Project Euler
Michael Kuyumcu
at www.projecteuler.net, one finds more than 300 interesting
programming challgenges from the field of number theory. Each program
is supposed to return a result to any problem within one minute - at
least every problem is guaranteed to be solvable by such a short
program, provided the approach is efficient. The difficulty of the
problems ranges from quite easy to extra hard. The easiest problem was
solved by more than 140,000 people, while the hardest (one of the most
recent ones) by only 88 people world-wide.
Maybe you would be interested to have a look at this great site. I
wonder how many of those problems could be solved with a hp
calculator.
Regards,
Dave
> Dear group,
>
> atwww.projecteuler.net, one finds more than 300 interesting
I think I've done a couple of them that way. I'd have to dig through
the programs on my 48SX to see if I still have them. A number of the
problems require fairly large data structures and input sets, though,
putting them out of the league of the 48 (unless you've got a large
RAM card and plenty of time to wait for a result). I'd bet the 200LX
has the muscle to tackle most of them with a bit of efficient C code.
-Dave Britten
Nemo
Hi, the first one with equation writer on 50g :
'S(n=1,999/3,3*n)+S(n=1,999/5,5*n)'
266333
where S is the Sigma symbo
Virgil
<ec817118-b224-49b4...@k22g2000yqh.googlegroups.com>,
Dave <david...@gmail.com> wrote:
The first one can easily be done on a 48. I did it on a 50, but used
only commands available on the 48.
--
woddo
Nemo, you must subtract the repeated numbers that are multiples of 3
and 5.
'S(n=1,999/3,3*n)+S(n=1,999/5,5*n)-S(n=1,999/3*5,3*5*n)'
166833+99500-33165
Michael Kuyumcu
I solved a couple myself, if on a normal PC, and the largest data
structures provided with the problems have, so far, been a 80 x 80
matrix of 4-digit numbers, and a list of 2000 common English words.
Both should fit onto any SD card. I don't know how much internal
memory the 48 has, since I only use a 49g+, and the latter would be
able to handle these in RAM. A different story would be the data
structures created by the program. Typical beginner-brute-force
attempts at solving will use a fair amount of memory, but studying
more efficient ideas for solutions usually yielded data structures
that could be accomodated by the 49g+. I really think the quality of
the idea is the determining factor for memory usage - and speed as
well.
Regards,
Michael Kuyumcu
Nemo
You're right, even if the problem "Find the sum of all the multiples
of 3 or 5 below 1000." is a bit ambiguous but your interpretation
(distincts numbers) seems more logical. Note that you can extract the
multiplication of the sum for better speed.
3*S(n...)+5*S(n...)-15*S(n...)
But it is still rapid 50G
oliverue
An RPL calc should be suitable to solve quite a few of these problems,
and provide some short neat solutions.
I did a few of the problems. #97 I could just type in. A few more took
only a handful of lines of code.
I got by #179 on my chinny-chin-chins with a brute-force method.
(Slow, but easy and it worked.)
The tenor through many of these problems seems to be, that while you
may solve them brute-force, they can be solved cleverly, for much
lesser compute and memory needs.
Thousands of users and submissions, in 53 languages, yet RPL is
absent... hmm.
Virgil
<4d9fc804-a8a2-4389...@e35g2000yqc.googlegroups.com>,
Nemo <carpenti...@free.fr> wrote:
Doesn't your formula count multiples of 15 twice, where they ought to be
counted only once?
--
Nemo
> In article
> <4d9fc804-a8a2-4389-8a32-687d4f7f3...@e35g2000yqc.googlegroups.com>,
yes ;) I was wrong
woddo gives the right formula.
Michael Kuyumcu
Nice project, indeed. I have been quite hooked with it since last
summer, when I spent a big part of my annual holidays to solve some of
the problems.
Brute force will not succeed for many of the problems with a higher
number, above 300, for instance. Which really motivates me to research
on the web, in number theory books, etc. Like you I think that the in-
built CAS of the hp pocket calculators can replace dozends or, in some
cases, hundredes lines of self-brewed code. Another reason to be a bit
proud of these great calculators...
Have you noticed that you can sort users by country or programming
language? You even get a "ranking" according to the number of problems
you solved. I am still in the "Novice" realm, but have hope to advance
to the next polyhedron before the end of this year...
Regards
val
> I wonder how many of those problems could be solved with a hp
> calculator.
Nice site.
One minute in a 2GHz 1Gb RAM 32 bits computer is how much time in an,
say, HP48GX 4MHz 128k RAM, 4 bits ?
Months ?
Michael Kuyumcu
The authors of the site state that the running time of under one
minute is for "moderately powered computer"s. Given an efficient
approach, most problems finish in under one minute even on an old
Pentium I (on my laptop). It's really not the hardware with most
problems there, but the software idea (the programmer's brain). Take,
for instance, Project Euler problem 321, "Swapping counters" (http://
projecteuler.net/index.php?section=problems&id=321). Once you have
managed to find out how many moves are necessary in this game to have
all of the n counters change position, one has to determine which of
these move numbers are triangle numbers. Searching through them
(a.k.a. "brute force") will cost you weeks or months or years even on
a modern high-end PC. With a more efiicient approach, though, the
program runs in less than 1/100 second on a modern PC. And that is
quite another order of magnitude, one of which hp calculators are
quite capable. RAM needed: a couple hundred bytes!
Once you solved a relatively recent problem, you are granted write
access to the (publicly not visble) problem forum where the first 100
solvers of this problem exchange their ideas and code fragments. It is
amazing how much more efficient many problems can be solved.
val
Interesting. I gave it my afternoon, trying to solve the counter
swapping problem.
So, after actually playing with counters it seems that the best
strategy requires 1+2+...+n+n+n+ ...3+2+1 moves, that is n+2*n*(n+1)/2
= n(n+2)
Triangular numbers are sum of natural numbers, and thus of the form
k(k+1)/2
We thus have to solve the Diophantine equation
2n(n+2)=k(k+1)
that is 2n2 -k2 +4n -k =0
whose solution is :
n' = 3n + 2k + 3
k' = 4n + 3k + 5
I don't have the skill to solve Diophantine equation but found a solver
on the net :) http://www.alpertron.com.ar/QUAD.HTM
giving 1 10 63... or 3 22 133... depending if we start from
n0,k0=1,2 or n0,k0=3,5
Hence the following program to find S(40)
CSWAP
<< 'S' STO 'K' STO 'N' STO
1 19 START
N 3 * K 2 * + 3 +
N 4 * K 3 * + 5 +
'K' STO DUP 'N' STO S + 'S' STO
NEXT
S
>>
and run 1 2 2 CSWAP 3 5 2 CSWAP +
2.47043313195E15
(We have to run it twice because the recurrent relation gives N_n+2
from N_n and K_n, and not N_n+1).
To find the lowest digits one can modify the above program by inserting
1E8 MOD before each of the three 'X' STO.
That gives 131 948 040
Hence the answer : 2 470 433 131 948 040
Is that the correct answer ?
In any case I agree with you, it is not a matter of brute-force and the
computation time in the above was just a couple of seconds.
Thank you for this nice puzzle.
Michael Kuyumcu
>
> giving 1 10 63... or 3 22 133... depending if we start from
> n0,k0=1,2 or n0,k0=3,5
>
> Hence the following program to find S(40)
>
> CSWAP
> << 'S' STO 'K' STO 'N' STO
> 1 19 START
> N 3 * K 2 * + 3 +
> N 4 * K 3 * + 5 +
> 'K' STO DUP 'N' STO S + 'S' STO
> NEXT
> S
>
>
>
> and run 1 2 2 CSWAP 3 5 2 CSWAP +
> 2.47043313195E15
> (We have to run it twice because the recurrent relation gives N_n+2
> from N_n and K_n, and not N_n+1).
>
> To find the lowest digits one can modify the above program by inserting
> 1E8 MOD before each of the three 'X' STO.
>
> That gives 131 948 040
>
> Hence the answer : 2 470 433 131 948 040
>
> Is that the correct answer ?
>
> In any case I agree with you, it is not a matter of brute-force and the
> computation time in the above was just a couple of seconds.
>
> Thank you for this nice puzzle.
Wow! It took me several *days* to ponder and finally solve this
problem, the easy part of course being finding the formula for the
number of moves. Then I, due to lack of deeper number-theoretical
knowledge, went for a brute-force like approach, but of course had to
discover in the process that it was futile. As I had read about the
Pell equation solver you mentioned (some earlier Project Euler problem
had had me solve a simpler, more specialized Pell equation, involving
continued fractions), I resorted to have it provide me with a
recurrence relation for the solutions, and implementing that was
really quick. In my implementation, I run only once through the values
from 0 to 39, alternating between to seeds to feed the recurrence
generator, depending on whether the loop index modulo 2 was 0 or 1.
Your answer is definitely correct, at least the Project Euler web site
told me so. Now that your solution is here on the web, I am sure some
lazybones will find it when they scour the net for easy solutions...
In the problem forum for this particular problem (#321), another
interesting approach emerged, focusing on the ratios between
corresponding pairs of move numbers and triangle numbers. There were
actually two rations, for even numbers of counters and for odd
numbers, and even with standard precision, these ratios were precise
enough to generate, with a bit of guess work around the estimated Pell
solutions, all of them within a fraction of a second (on a modern PC).
May I ask about your background in mathematics? Do do you it
professionally? I teach it to children and youth at a public school,
but number theory had never been my strong suit during my time at the
university. It has only been 3/4 of a year now that the material has
been coming alive within me, getting to a point where it just keeps
working inside me even when I am swimming or relaxing.
Anyway, glad you liked the problem.
Regards,
GWB
> Note that you can extract the
> multiplication of the sum for better speed.
> 3*S(n...)+5*S(n...)-15*S(n...)
> But it is still rapid 50G
I remembered how Gauss solved a similar problem (when he was 6 or 7!)
and came up with the following:
S = n1*(n1 + 3)/6 + n2*(n2 + 5)/10 - n3(n3 + 15)/30
where
n1 = greatest divisor of 3 <= n;
n2 = greatest divisor of 5 <= n;
n3 = greatest divisor of 15 <= n
In this case, n = 999. Then
S = 999*(999 + 3)/6 + 995*(995 + 5)/10 - 990*(990 + 15)/30
S = 166 833 + 99 500 - 33 165
S = 233 168
Regards,
Gerson.
Nemo
Hi,
Problems 1 to 10 solved in UserRPL HP50G (with emu48 fast mode )
Nemo
pb 11 solved, with some luck ;) ( Not all diags were analysed ...)
For clues, I uses some SEQ, imbricated DOSUBS and AXL commands... 40
s. with emulator full speed.
Nemo
> On May 6, 2:51 pm, Nemo <carpentier.gil...@free.fr> wrote:
>
> I remembered how Gauss solved a similar problem (when he was 6 or 7!)
> and came up with the following:
>
> S = n1*(n1 + 3)/6 + n2*(n2 + 5)/10 - n3(n3 + 15)/30
>
> where
>
> n1 = greatest divisor of 3 <= n;
> n2 = greatest divisor of 5 <= n;
> n3 = greatest divisor of 15 <= n
(...)
> Regards,
>
> Gerson.
:D beautiful !
GWB
>
> :D beautiful !
Thanks! However that's essentially the same formula in the wikipedia
article below, as I found out later:
http://en.wikipedia.org/wiki/Project_Euler
Regards,
Gerson.
Nemo
I've a problem with the "Problem 19" :
http://projecteuler.net/index.php?section=problems&id=19
Here an exemple of RPL code (HP50G but must work with 48)
«
0.
.001901 .002000 FOR a
.01 .12 FOR m
1. m a + + 12.00 TSTR
1 3 SUB "SUN" SAME { 1 + } IFT
.01 STEP
.000001 STEP
»
But this prg don't give the right answer ( on Sunday difference ...).
I Dont understanf why !
val
>
> Wow! It took me several *days* to ponder and finally solve this
> problem, the easy part of course being finding the formula for the
> number of moves. Then I, due to lack of deeper number-theoretical
> knowledge, went for a brute-force like approach, but of course had to
> discover in the process that it was futile. As I had read about the
> Pell equation solver you mentioned (some earlier Project Euler problem
> had had me solve a simpler, more specialized Pell equation, involving
> continued fractions), I resorted to have it provide me with a
> recurrence relation for the solutions, and implementing that was
> really quick. In my implementation, I run only once through the values
> from 0 to 39, alternating between to seeds to feed the recurrence
> generator, depending on whether the loop index modulo 2 was 0 or 1.
>
We have more or less the same method. I don't know Pell equation but I
suppose it is a quadratic Diophantine equation as well, and that you
have to distinguish between odd and even numbers.
> Your answer is definitely correct, at least the Project Euler web site
> told me so. Now that your solution is here on the web, I am sure some
> lazybones will find it when they scour the net for easy solutions...
> In the problem forum for this particular problem (#321), another
> interesting approach emerged, focusing on the ratios between
> corresponding pairs of move numbers and triangle numbers. There were
> actually two rations, for even numbers of counters and for odd
> numbers, and even with standard precision, these ratios were precise
> enough to generate, with a bit of guess work around the estimated Pell
> solutions, all of them within a fraction of a second (on a modern PC).
>
> May I ask about your background in mathematics? Do do you it
> professionally? I teach it to children and youth at a public school,
> but number theory had never been my strong suit during my time at the
> university. It has only been 3/4 of a year now that the material has
> been coming alive within me, getting to a point where it just keeps
> working inside me even when I am swimming or relaxing.
I'm physicist so I have a general interest in maths. I knew about the
existence of Diophantine equation but never encountered those in a
specific problem. It's really nice to discover maths this way, by
trying to solve problems. Thanks for giving this site to us !
Nemo
I've found the problem. Flag 42 must be set
Nemo
I've resolved 22 problems with the 50G ( in fact with HPUSEREDIT +
emulator) :
1..13-15-16-19..21-25-29-48
I was unable to solve the problem 14 with a trivial algorithm (too
slooooow on the 50) and dont find any trick.
http://projecteuler.net/index.php?section=problems&id=14
The problem 17 seems easy, but my english is too poor ;)
"If the numbers 1 to 5 are written out in words: one, two, three,
four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in
total. If all the numbers from 1 to 1000 (one thousand) inclusive were
written out in words, how many letters would be used? "
http://projecteuler.net/index.php?section=problems&id=17
This site is very interesting. But the recents problems seems much
more complicated than the olds
Michael
> On May 5, 8:37 pm, Michael Kuyumcu <i...@noemanetz.de> wrote:
>
>
>
>
>
>
>
>
>
> > Dear group,
>
> > atwww.projecteuler.net, one finds more than 300 interesting
> > programming challgenges from the field of number theory. Each program
> > is supposed to return a result to any problem within one minute - at
> > least every problem is guaranteed to be solvable by such a short
> > program, provided the approach is efficient. The difficulty of the
> > problems ranges from quite easy to extra hard. The easiest problem was
> > solved by more than 140,000 people, while the hardest (one of the most
> > recent ones) by only 88 people world-wide.
>
> > Maybe you would be interested to have a look at this great site. I
> > wonder how many of those problems could be solved with a hp
> > calculator.
>
> > Regards,
>
> I've resolved 22 problems with the 50G ( in fact with HPUSEREDIT +
> emulator) :
> 1..13-15-16-19..21-25-29-48
>
> I was unable to solve the problem 14 with a trivial algorithm (too
>
> The problem 17 seems easy, but my english is too poor ;)
>
> "If the numbers 1 to 5 are written out in words: one, two, three,
> four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in
> total. If all the numbers from 1 to 1000 (one thousand) inclusive were
> written out in words, how many letters would be used? "http://projecteuler.net/index.php?section=problems&id=17
>
> This site is very interesting. But the recents problems seems much
> more complicated than the olds
The recent problems (many, but not all of them) are more difficult,
yes. But if you develop a good idea, many of them can be solved within
seconds. This is what I like about the problems, a clever idea is
rewarded.
Regards,
Michael
>
>
>
>
>
>
>
>
>
> > Dear group,
>
> > atwww.projecteuler.net, one finds more than 300 interesting
> > programming challgenges from the field of number theory. Each program
> > is supposed to return a result to any problem within one minute - at
> > least every problem is guaranteed to be solvable by such a short
> > program, provided the approach is efficient. The difficulty of the
> > problems ranges from quite easy to extra hard. The easiest problem was
> > solved by more than 140,000 people, while the hardest (one of the most
> > recent ones) by only 88 people world-wide.
>
> > Maybe you would be interested to have a look at this great site. I
> > wonder how many of those problems could be solved with a hp
> > calculator.
>
> > Regards,
>
> I've resolved 22 problems with the 50G ( in fact with HPUSEREDIT +
> emulator) :
> 1..13-15-16-19..21-25-29-48
>
> I was unable to solve the problem 14 with a trivial algorithm (too
>
> The problem 17 seems easy, but my english is too poor ;)
>
> "If the numbers 1 to 5 are written out in words: one, two, three,
> four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in
> total. If all the numbers from 1 to 1000 (one thousand) inclusive were
> written out in words, how many letters would be used? "http://projecteuler.net/index.php?section=problems&id=17
>
> This site is very interesting. But the recents problems seems much
> more complicated than the olds
On problem 14: I have programmed a relatively fast implementation on
the 49g+ that uses a list with 1000 (or even 10000) elements to cache
old step numers. For instance, since 1 needs 0 steps to finish, 2
needs 1 step to finish, 3 needs 7 steps, and so on, my list stores
{0,1,7...}. So then, whenever a number falls below, say 1000, I look
up the remaining steps to finish in the list. That makes the program
much faster. You can save on storage space if you use the fact that
the for even numbers, the step count needed to finish is 1 + the step
count of half the number.
Regards,
Nemo
Yes 25 problems resolved ;) PB22 was the last one. I can't post the
sources on Euler Projects because all theses old topics are archived.
My prefered are pb 18 and 67 :
http://projecteuler.net/index.php?section=problems&id=18
http://projecteuler.net/index.php?section=problems&id=67
It was a real pleasure when i discovered the trick without internet
search. Like an illumination lol
2 lines and 76.5 bytes in User RPL ;)
Nemo
>
> It was a real pleasure when i discovered the trick without internet
> search. Like an illumination lol
>
> 2 lines and 76.5 bytes in User RPL ;)
In fact it's 71,5 bytes only :
«
« SWAP 0 OVER OBJ-> NIP ->LIST MAX ADD » STREAM
« MAX » STREAM
»
For pb 67, must works in exact mode for less memory usage
Nemo
the first RPL source. It's done with the 329 problem :
http://projecteuler.net/index.php?section=forum&id=329&page=3#36068
Nemo
> I tried to resolve a recent problem in Euler projet to post perhaps
> the first RPL source. It's done with the 329 problem :http://projecteuler.net/index.php?section=forum&id=329&page=3#36068
Oups !
http://projecteuler.net/index.php?section=problems&id=329
The other link is accessible only if you solved the problem.
val
Nice very short program !
Can you tell us how the one-hundred rows triangle is entered on the
stack ?
oliverue
> In fact it's 71,5 bytes only :
>
> «
> « SWAP 0 OVER OBJ-> NIP ->LIST MAX ADD » STREAM
> « MAX » STREAM
> »
>
With my input a list of vectors, here's my version:
≪ OBJ→
2 SWAP START
2 ≪ MAX ≫ DOSUBS
+
NEXT
≫
I'm getting the 100-row triangle into my calculator with a few lines
of JavaScript that fetch the data from the official URL, and massage
it into an array of array of numbers.
Run-time for #67 is under a second on ND1 (on iPhone), and that
includes the time to fetch the data (15 KiB).
I'm going to post a "Project Euler" shared folder in the next few days
with the solutions to a bunch of problems.
oliverue
> the 49g+ that uses a list with 1000 (or even 10000) elements to cache
> old step numers.
Michael, are you running this on a 50g (or Emu48) with the *full* one
million iterations?
I coded this up in RPL+
≪ 0 =longest
[] =cache @ length of chain at num
1 =cache[1] @ length for num 1
2 1e6 1 - FOR i
i
0 =steps
DO
IF DUP isEven
THEN 2 / ELSE 3 * ++ END
++steps
UNTIL
DUP =:cur i <
END
DROP
cache[cur] steps + =steps
steps =cache[i]
IF steps longest >
THEN steps =longest i =index END
NEXT
index
≫
and it takes a full 5 minutes to run on ND1, using a cache of a
million elements.
Can't see how this could run under an hour (or two) in User RPL on a
50g.
Caching not just previous iteration results, but any encountered, may
improve things quite a bit.
In my mind, this problem really asks you to use a hash-table, and I'm
leaning toward adding hash-table support to RPL+, because it's often
very handy to have.
As ND1 can also run JavaScript programs, I often compare RPL against
it. The JavaScript implementation analog to above runs a full 34x
faster, resulting in an overall run-time of 7.8s.
This problem is a bit of a worst case for RPL and it lends itself very
much to native languages, as it doesn't require non-native types. I
suppose one could get this to complete in a few seconds on a 50g,
using HPGCC.
(Btw, I'm finding Project Euler problems that run almost as fast in
RPL as in JavaScript. And some are among the most concise in
comparison with those posted by others in other languages on the
solution threads. (E.g., can hardly beat ≪2e6 primes ≪+≫ STREAM≫ (#10)
for length.))
Nemo
Oliverue, I dont understand how works your program ... What input
data format is used ?
This Euler website is a little addictive lol... I've resolved 29 pb
(but dont care about the 1mn run time but many of thems needs less
than 1 mn ) .
I've spends time about the PB328 but without success :(
http://projecteuler.net/index.php?section=problems&id=328 )
I have an idea for the pb014 (a trivial algorithm is to slow in User
RPL, but it would be easy in assembler)
I would be cool to have some improvement if RPL will have a futur in
an HP51 ;) Easy insertions in lists, apply a prog to only one item or
subsets of items etc. And of course some speed progress. Must say that
add or delete items in a list is slow. Also division of 'infinite'
integers ...
oliverue
> > 2 SWAP START
> > 2 ≪ MAX ≫ DOSUBS
> > +
> > NEXT
> > ≫
>
> > I'm getting the 100-row triangle into my calculator with a few lines
> > of JavaScript that fetch the data from the official URL, and massage
> > it into an array of array of numbers.
> Oliverue, I dont understand how works your program ... What input
> data format is used ?
We're apparently using different representations for our input data,
as mine doesn't work with your prg, and I, too, couldn't figure out
how your prg works...
For #18 and #67 my input is a list of arrays, so { [75] [95 64] [17 47
82] ... }
On the 50g, you may have to replace "+" with "ADD" in the given code.
> I've spends time about the PB328 but without success :(http://projecteuler.net/index.php?section=problems&id=328)
Looks pretty hard. Good, though, that you're given a data point to
check against. Good luck with this problem!
I've been biting my teeth out with #304. But I really like these
problems because they push my engine.
As a result of working on this problem, I now have very efficient
matrix exponentiation in ND1/MorphEngine.
You remember our quest for Fibonacci numbers elsewhere (FibTriangle),
now it's possible to compute Fibonacci(1E14) MOD someNumber in
basically no time. (Even WolframAlpha bails at that...)
This works via [[0 1][1 1]] 1E14 POWMOD.
I also learned that HP was a bit lazy with their POWMOD
implementation, for matrix args. While implemented, they do the modulo
operation on the result only (not intermediate stages), so [[0 1][1
1]] 10000 POWMOD already yields an "Integer too large" error, reducing
the usability of this function.
Also, NEXTPRIME is dreadfully slow for large numbers. In #304, you're
asked to generate one hundred thousand subsequent primes greater than
1E14, compute the Fibonacci number for each, and sum them up. A bit of
a problem, if it takes 0.5s for *each* prime alone... (on Emu48! I
guess several seconds on the 50g.)
> I have an idea for the pb014 (a trivial algorithm is to slow in User
> RPL, but it would be easy in assembler)
A solution is in the post above (should be easy to adapt to RPL from
RPL+). It's not brute-force, but as long as you have to do anything in
a loop millions of times, you're quickly in the "hours of run-time"
territory on the 50g, I fear.
> I would be cool to have some improvement if RPL will have a futur in
> an HP51 ;) Easy insertions in lists, apply a prog to only one item or
> subsets of items etc. And of course some speed progress. Must say that
> add or delete items in a list is slow. Also division of 'infinite'
> integers ...
MorphEngine is throwing in a whole lot of new commands, such as
"insert" and "remove" for arrays. (Plus you notice the [] operator in
RPL+ for easy access to arrays.)
The biggest enhancement, however, is that there's no longer a
distinction between lists and vectors. This implies that you can do
anything to a vector that you could only do to a list on 50g.
Oliver
Andreas Möller
> I would be cool to have some improvement if RPL will have a futur in
> an HP51 ;) Easy insertions in lists, apply a prog to only one item or
> subsets of items etc. And of course some speed progress. Must say that
> add or delete items in a list is slow. Also division of 'infinite'
> integers ...- Zitierten Text ausblenden -
given the fact that
- there has been no ROM-Update in over two years now
- the hardware which was the reason for the last ROM update
(StreamSmart) is not available
- almost no attempts have been made to upgrade/strengthen the HP 50g
in the last two years
you can make up your own mind how much interest the Hewlett-Packard
Company has in their graphic calculators.
The only "progress" that has been made, is that in Spain you can buy a
blue HP 50g now.
Regards,
Andreas
http://www.software49g.gmxhome.de
Joel Koltner
news:eb7bdcf8-ad2d-44e8...@p13g2000yqh.googlegroups.com...
>The only "progress" that has been made, is that in Spain you can buy a
>blue HP 50g now.
Hmm... interesting they chose Spain as, apparently, the test market!
So how about you, Andreas? -- You're clearly a very good programmer... any
plans to start applying your skills to, e.g., Android or iOS devices or other
mobile platforms?
Nemo
> > > ≪ OBJ→
> > > 2 SWAP START
> > > 2 ≪ MAX ≫ DOSUBS
> > > +
> > > NEXT
> > > ≫
>
> > > I'm getting the 100-row triangle into my calculator with a few lines
> > > of JavaScript that fetch the data from the official URL, and massage
> > > it into an array of array of numbers.
> > Oliverue, I dont understand how works your program ... What input
> > data format is used ?
>
> We're apparently using different representations for our input data,
> as mine doesn't work with your prg, and I, too, couldn't figure out
> how your prg works...
>
> For #18 and #67 my input is a list of arrays, so { [75] [95 64] [17 47
> 82] ... }
> On the 50g, you may have to replace "+" with "ADD" in the given code.
>
> Oliver
OK ;) I think i've understand. My strategy is top to bottom, yours is
bottom to top.
1/ Top to bottom (seems more 'natural'?) : Begin with the top line -1
of the triangle and go to the bottom . For each item in line n, add
the max of the two items of line n+1 that could 'go' to this place.
Arrived to the bottom get the max item
2/ Bottom to top (clearly more efficient and simple) : Begin with
bottom line and go to the top. Take the max of 2 successive items of
the line n and add it to the corresponding item of the line n+1
No time to try now, but a real HP50 version could be
{ {75 0 0 } {95 64 0} {17 47 82} ... }
≪ OBJ→
2 SWAP START
≪ MAX ≫ DOSUBS ADD
NEXT
≫
No need of 2 before MAX, but probably problems (insuficiants arguments
error) with { 2 } << MAX >> DOSUBS ( I add addiationals 0 for this)
oliverue
> 2/ Bottom to top [...] Take the max of 2 successive items of
> the line n and add it to the corresponding item of the line n+1
>
I trust you meant to say "line n-1".
> { {75 0 0 } {95 64 0} {17 47 82} ... }
You're correct to point out that it has to be a list of lists for 50g
(sorry, I'm in the habit of writing everything with [] in ND1). But,
don't pad the lines! That wouldn't work. The beauty of << MAX >>
DOSUBS is, that it reduces each line n by one to the size of line n-1,
so they can be added. We're successively getting shorter until the
last addition, which is {75} {xxx}.
>
> ≪ OBJ→
> 2 SWAP START
> ≪ MAX ≫ DOSUBS ADD
> NEXT
> ≫
>
> No need of 2 before MAX, but probably problems (insuficiants arguments
> error) with { 2 } << MAX >> DOSUBS ( I add addiationals 0 for this)
You're right about the 2 being optional on 50g. I prefer to write it
for clarity, and it works either way on the 50g. There's no
insufficient arg problem because we're not doing << MAX >> DOSUBS on
line 1. That's owing to the START loop starting at 2.
If you get a chance to run this with the big triangle on the 50g, I'd
appreciate hearing what the run-time is, for my little benchmark
table.
Cheers.
oliverue
official big (15 KiB) triangle data from Project Euler and make it an
array of array of numbers in ND1:
function() {
var data = requestURL("http://projecteuler.net/project/
triangle.txt").split("\r\n");
return data.map(function(x){return x.split(" ").map(function(x)
{return +x;});});
}
This function is stored in a variable ('#67_data') in the same folder
as the code above.
So, my entire code for problem #67, which includes fetching and
formatting the input, looks like this:
≪ #67_data OBJ→
2 SWAP START
2 ≪ MAX ≫ DOSUBS
ADD
NEXT
V→
≫
(Note that RPL calls JavaScript, as if it were RPL.)
Nemo
>
> If you get a chance to run this with the big triangle on the 50g, I'd
> appreciate hearing what the run-time is, for my little benchmark
> table.
>
> Cheers.
Hi, The results are :
Real calc
@ Real mode - Approx = 71.6_s (there is enough memory : 167251 bytes
free)
@ infinite integer mode - Exact = 171.8_s
@ Binary mode = Error : the MAX function don't works with binary
( #54d ...}
Emulator (Emu48 1.46 on ThinkPad X300)
@ Real Mode/Approx = 4.23_s
@ Infinite integer -Exact = = 8.06_s
( the Emu48 emulation of infinite integer seems better than the ARM )
oliverue
> @ Real mode - Approx = 71.6_s
> Emulator (Emu48 1.46 on ThinkPad X300)
> @ Real Mode/Approx = 4.23_s
Thank you, Nemo!
For comparison: ND1: 0.9s, CalcPad/Mac (not publicly available yet):
0.06s.
(These timings include the time to fetch and prepare the input data.)
You mentioned BigNum division (or lack thereof) in an earlier post.
Did you need that for one of the Euler Project problems? If so, which
one? (I may want to give it a shot.)
Michael
> > On problem 14: I have programmed a relatively fast implementation on
> > the 49g+ that uses a list with 1000 (or even 10000) elements to cache
> > old step numers.
>
> Michael, are you running this on a 50g (or Emu48) with the *full* one
> million iterations?
>
Hi Oliverue,
I'm running it on a physical 49g+ machine. Somehow the simulator
really doesn't seem to be so nice since I like programming on a pocket
calculator. If I'm at a full-blown PC, there are, I think, better
programming environments. By the way, have you tried out the J
programming language (http://www.jsoftware.com/stable.htm)? Using
this, some problems can be formulated even terser than with RPL (all
flavors), and many of the Project Euler problems have been solved with
J programs of one, two or a little more lines.
Anyhow, I only implemented only the Collatz algorithm (that you
programmed in RPL+, which looks promising, but how do I get it onto
the 49g+?) and the lookup routine for the cached values, not the
Project Euler problem itself. By the way, I think the number of steps
for the starting number 1 should be "0", not "1", in your code, since
there is no operation necessary to reach the destination 1. I would
imagine that the program would get quite slow for bigger inputs. I
usually have the students in my class, after they have experimented
with the Collatz procedure a while, try to find the starting number
with the most steps to reach 1, in the "birthday range", from 1 to
31052000. To check their answers, I bring my hp 49g+ to class and type
in their starting numbers.
Maybe one should code this up in System RPL. Should be fast enough, I
guess.
Regards,
oliverue
> Somehow the simulator
> really doesn't seem to be so nice since I like programming on a pocket
> calculator.
I hear ya. I love programming on the device, too. To me the point of a
calculator is having it close by and being able to transcribe
thoughts, without the fuss of a computer. Most of PE problems I solved
so far where coded on the device.
> By the way, have you tried out the J programming language...
I've admired it from afar. Then I admired GolfScript from afar (which
is *even* terser). And then I began to implement latter in MorphEngine
(the calculator engine behind ND1 and upcoming calcs), as a 3rd
language choice. I think I'm a week away from a releasing a first cut.
For your terse code enjoyment, here're solutions for just a few
Project Euler problems in "GolfScript/MorphEngine" (which is the union
of GolfScript with the MorphEngine 400-instruction set):
#5: 21,tail{lcm}*
#6: 101,tail.{+}*SQ\SQ{+}+-
#7: 2{NEXTPRIME}10000*
#10: 2000000primes{+}*
#18, #67 (the ones from above discussed with Nemo): →{2{max}DOSUBS+}1-
*
> ... but how do I get it onto the 49g+?
Sorry. ND1 (and free ND0) are currently the only calcs that will run
RPL+.
I think it would be possible to support it on 49, 50g with a RPL+ to
UserRPL+SysRPL translator, but nobody's stepped forward to implement
such.
This year, MorphEngine calcs will appear on Android, Kindle and Mac/
Win, supporting RPL+.
> By the way, I think the number of steps for the starting number 1 should be "0", not "1"...
You're quite right. It doesn't make a difference in finding the number
which has the longest chain, but the chain length is biased by one. I
corrected this. Thanks.
> Maybe one should code this up in System RPL. Should be fast enough, I guess.
I think so, too. Maybe someone with SysRPL skills is listening?
> Regards,
Cheers.
Michael
Thanks for pointing out GolfScript to me. Looks interesting, while a
bit limited. The approach seems to have been abandoned, judging from
the web site; the last post dates back from 2008. Do you have a
pointer to MorphEngine 400 for me? Thanks.
Regards,
oliverue
Actually, some people engage in an obscure hobby called "code
golfing" (just slightly less obscure than hacking HP calculators in
the year 2011...), where GolfScript is all the rage.
It's very actively used in that "sport" and so successful, that those
who don't know it, frequently whine about it providing an "unfair"
advantage over "real" programming languages.
http://meta.codegolf.stackexchange.com/questions/88/on-golfscript-and-language-bigotry
http://stackoverflow.com/questions/3903439/golfscript-a-practical-example
The official website hasn't been updated, I think, because the
language is *done*. It's small, and it does what it says it does, and
there's no library (that would typically grow in time).
> Thanks for pointing out GolfScript to me. Looks interesting, while a bit limited.
Limited, yes. You certainly wouldn't want to write a big program in
GolfScript, but it's surprising how versatile and powerful it is. It
has all the list processing functionality that a 50g has, and more.
Code golfing is the art of solving a compute task with the absolute
fewest number of characters of code, and GolfScript pretty much has
the edge currently.
But, yes, it is true that GolfScript feels like a language designed
for this singular pursuit, and it completely lacks functionality
typically provided by libraries, limiting its scope.
That, of course, is where MorphEngine comes in (in the context of
computational math code).
> Do you have a pointer to MorphEngine 400 for me?
Approx. 80% of the MorphEngine instruction set is a subset of the
50g's instruction set (and the exact same data types), so you know it
already. The remaining 20% are functions (and data types) that the 50g
lacks, but which make sense as natural extensions (or so I think).
Examples for that second group are: "primes" (a sieve), loggamma, PDFs
besides NDIST, quantiles; array manipulations like permutate, insert,
remove, union, complement; string manipulations like find, split; etc.
Also notable: lists and vectors are unified. You can do with vectors,
what you can only do with lists on HPs. You can, for example, do "[1 2
'A' 4] sin" (which doesn't work on a 50g).
GolfScript doesn't know "lists", but is all about arrays. So, with the
MorphEngine instructions added, all the typical math functions are
suddenly available.
In the examples given above, "lcm", "primes", "tail", "SQ",
"NEXTPRIME", "max" are MorphEngine instructions (all but one you know
from your HP).
To learn or play with MorphEngine, learn or play with ND1:
http://naivedesign.com/ND1/Specs.html
An iPad MorphEngine "calculator", CalcPad, is up next.
This page has a naked summary of the instructions:
http://naivedesign.com/ND1/ND1_Reference__Function_Summary.html
GolfScript is implemented as just another language in ND1. So you can
call it from RPL programs, just like JavaScript. You can also invoke
it from JavaScript, and you can call your own RPL or JavaScript
functions from GolfScript--all without syntactical overhead. The point
is to provide one more choice to help shortening the path from idea to
realization.
For example, when I need a vector from 1 to 100 in ND1, I just key in
"gs:100," EVAL. If I want to quickly fold a vector, I type "gs:
{myFoldOp}*". This could also be done in RPL, but on a mobile device
the number of keystrokes count. It just makes using the calc more
efficient (and it's fun!).
Be cautioned that ND1 is (so far) substantially less complete than a
50g. It doesn't have solver yet, nor most CAS functionality. (Both of
which will come.) So, it's not a substitute.
But, given that it's often hundreds of times faster than a 50g (see
the benchmarks in the "Comparison to HP Calculators" doc, off the
Specs page) and can deal with MBs of data, which is easily acquired
over WiFi, it's quite well suited for Project Euler problems.
Cheers.
Michael
> > The approach seems to have been abandoned, judging from the web site;
>
> Actually, some people engage in an obscure hobby called "code
> golfing" (just slightly less obscure than hacking HP calculators in
> the year 2011...), where GolfScript is all the rage.
> It's very actively used in that "sport" and so successful, that those
> who don't know it, frequently whine about it providing an "unfair"
> advantage over "real" programming languages.
>
Thanks. I see your points about GolfScript. The idea appeals to me,
the web site doesn't. How do I get GolfScript running? I presume it is
a C# program that will need to be compiled by, say Visual Studio or
the like, and then --- ?
I look forward to your MorphEngine implementation. If there was a
faster, more versatile (memory...) substitute for the 50g, I would
even consider using a smartphone :)
Regards,
oliverue
No need to do any compiling, as GolfScript runs atop Ruby. (Ruby is
built into Macs. Surely easily available for PCs, too.)
On http://www.golfscript.com/golfscript/builtin.html click Download
and run Ruby on the downloaded .rb file. Key in your GolfScript code
and terminate input (Ctrl-D on Mac). It may be best to learn from the
plentiful code golf examples of others.
Yes, this interface is as bare-bones as it gets.
In ND1, you'll be able to type "gs:" followed by your GolfScript code.
Inputs come from, and outputs go to, the stack, which makes this way
more user-friendly, I think. (Note that the GolfScript implementation
in MorphEngine is a completely separate implementation. It doesn't use
Ruby.)
> If there was a
> faster, more versatile (memory...) substitute for the 50g, I would
> even consider using a smartphone :)
How about an iPod touch? Lacking the phone, you can think of it as a
little amazing computer, that's far more portable than a 50g. Just my
opinion, but I'm finding on-screen menus and a QWERTY keyboard much
more pleasant for code entry than rubber keys.
oliverue
1&5*)/}/1+`
http://stackoverflow.com/questions/2388254/code-golf-collatz-conjecture
Michael
> Michael, here's one for you: Collatz Conjecture in GS: ~{(}{3*).
> 1&5*)/}/1+`http://stackoverflow.com/questions/2388254/code-golf-collatz-conjecture
Oh well, that is quite concise :)
On my way into the GS universe, I tripped over "Funge" (and its
various flavors) - what a language. I must try that one, too! :)
Thanks your your input!
Regards,
oliverue
make it another language in ND1, sooner or later. It's very easy to
implement and there's even a super-nice implementation in JavaScript.
Check out this guy's language experiments: http://www.quirkster.com/js/
I think he's done a fantastic job. Ingenious idea of coding up his
email address.
To implement Befunge is unapologetically crazy, except one could
possibly say that it's actually a swell learning tool. Where else can
you graphically see a program execute?
I've seen a couple of Project Euler solutions in Befunge-93...
Michael
That are a couple of very nice Befunges, yes :) This weekend I will
try to code something in Befunge, and maybe one could code a RPL-to-
Befunge "cross compiler." That would certainly require a good working
knowledge of the Befunge language, so it should be a good opportunity
to learn.
You are quite resourceful a conversationalist, if I may say so... :)
Regards.
oliverue
The MorphEngine GolfScript implementation is a "cross-compiler" of
sorts: it translates GolfScript to RPL+ plus some GS bits, and then
executes that. It thereby leverages MorphEngine's byte-code compiler.
I say "of sorts" because, for the duration of the execution, it
reshapes the run-time environment to support the GS bits remaining in
the code stream.
As a side-effect you can run a "toRPL" command on your GS code object
and get it translated to RPL+. (That means, you can actually make GS
readable... ;-))
I think I'm going to release the code into the Public Domain, in case
you're interested.
Befunge could be built in the same way, and I would wage a bet that it
could be done in 50 lines of code.
I suppose Befunge is simple enough that it can be written w/o any
environment quite easily in just about any interpreted language that
supports something like a stack data type.
FWIW, in JavaScript, Ian's implementation could be made to interact
with ND1's stack by simply switching the stack variable over to
"calculator.stack" (an array onto which you can push() and pop()
items). That's for a minimal implementation. The nice thing he did, of
course, is the start/stop and visual feedback thing, which would
require a bit more work.
If you're interested to do anything related to this in MorphEngine,
please start a topic at http://forums.naivedesign.com and you shall
receive all needed support.
Cheers.
oliverue
Oops. Sorry. You talked about the other direction. I responded having
in my mind you wanted to cross-compile Befunge to RPL.
RPL-to-Befunge would be hard (think about translating a FOR-loop into
a 2-D thing) *and* of limited value, I think, because, what is RPL
without the rich command library of an HP calc?
Befunge to RPL, however, is easy because the Befunge commands all have
direct equivalents in RPL *and* it would be cool, because you could
run a new language on your HP calc. I did a quick check on hpcalc.org:
seems no-one did a Befunge interpreter yet.
Michael
> receive all needed support.
>
> Cheers.
Thanks for your kind offer, and while I would normally be interested
to program sort of abstruse interpreters, I really don't have the time
for that. At the moment, that is. Plus, I don't know a think about
MorphEngine. The more you tell me about it, though, the more intrigued
I get. I am even seriously considering getting an ND1-capable
smartphone as soon as your work is finished.
A RPL-to-Befunge cross-compiler would be useful for Project Euler. I
really would love to show off there with a solution to problem 335
(which I have solved in DECIMAL BASIC (runtime 20 ms), and could
easily translate to RPL, and then have it translated even further into
Befunge. And then post that solution. In addition, it's exactly the
difficulty of translating RPL constructs into Befunge (like a FOR
loop) that is so appealing to me. I'm a problem solver by heart, you
know :) Just look at the thread title... Although, as they say, one
who seeks problems will encounter problems... :) I - naively,
admittedly, imagine that translating a FOR loop into Befunge would
send the read/write head around in a circle until some condition for
breaking out of that loop sends him one layer up (or down, for that
matter). Trefunge, of course. I just can't wrap my head around why the
inventors have not considered an n-dimensional stack stack stack of n-
dimensional stack stacks. :)
Well, I must stop blabbering now. Yet I hope, our paths will cross
again, here or at one of your promising projects! As soon as I have
figured out how to code my private e-mail address in Befunge, I will
post it here. Weekend, come!
Greetings from the Befungeons dungeons,
Michael
And Whirl, I forgot to mention the Whirl programming language (check
out this interactive interpreter, if you are interested, at
http://www.bigzaphod.org/whirl/Whirl-1.01.swf ). How about having a
Befunge grid filled with Whirl instructions. That's more like it...
oliverue
You solved #335? Wow. My hat's off! I encourage you to pursue the
Befunge show-off idea.
Last blabbering language comments:
- Follow the funged path and you will find the n-dimensional stacks.
'twas my first thought, too, and apparently picked up by someone more
than a decade ago. I forget the name.
- Whirl did not resonate with me, but thanks for the link. The Readme
sure was fun to read.
- "Morph" in MorphEngine refers to morphing code. Arguably, it does
this already in places, but the vision is to get crazy speed by
identifying certain code bits in one language and (simplified speak
on) translating them into another for faster execution, up into the
native world and the GPU. (off)
- One nice thing about GS and Befunge is the simplicity with which
self-modifying code can be written.
Put these things together and imagine the following:
- A fungey grid populated with MorphEngine particles (ok: fancy speak
for good'ol RPL instructions, but in one-char form). Let's take one,
say, NEXTPRIME. As the interpreter steps on it, all hells breaks
loose, as the instruction is rippling through language layers
(premeditated by the byte-code compiler, of course) into the native
world where OpenCL engages all four cores of your Kal-El processor,
and the GPU, to crunch for the next prime. The result is propagated
back, until it neatly settles in the JavaScript stack waiting for the
next fungey action.
(Remember, as per note above: 0.5s *per* prime on 50g in the 1e14
range. The layer stuff is not a prohibitive expense. Matrix
manipulation and invariant-loop-in-loop are other, perhaps more
obvious, examples of benefactors of native code.)
Speed is universally useful.
One (somewhat wild) enabled application is automated algorithmic
composition:
Say a Project Euler problem is solvable in 10 GS/ME instructions (the
ones shown above are of length 3 to 9). Or you have a solution
template, but lack the middle part.
Now
- Employ RPL+ code distributing permutations of GS/ME particles into
templated funge grids. (Each holding potentially prospective paths of
code to be explored, with "openings" to receive the permutations.)
- Let it crunch.
Result: program that will solve your problem.
(blabbering now subsiding for good, for now...)
Thanks again, Michael, for the conversation and for pointing out the
site to us. Looks like you turned on a few of us. (I had heard of it,
but never invested the time to check it out. I'm glad I did.)
And may this thread survive the subversive language interception and
proceed with Euler talk... ;-)
Michael
Well, as for automated algorithm composition, I hereby blabber forth
my very, very last contribution to this contrived thread with funge-
fudge flavor: let the program "permutate" (rather: evolve)
instructions via a genetic algorithm, in the hope that the solution
might be found by zeroing in on a global optimum (provided the search
space is not too big. As Stephen Wolfram pointed out in "Another kind
of science", genetic algorithms basically use the concept of
constraints, which is only of limited usefulness for big search spaces
generally)
Off-grid now, really,
val
>
> A RPL-to-Befunge cross-compiler would be useful for Project Euler. I
> really would love to show off there with a solution to problem 335
> (which I have solved in DECIMAL BASIC (runtime 20 ms), and could
> easily translate to RPL,
A possible translation to RPL, if you have the ALG48 library installed
:
P335:
<<
4 SBR 8 *
3 SBR 9 *
2 SBR 24 * +
11 7 9 ^ MOD-
6 /
>>
SBR:
<<
1 18 FOR i 2 7 9 ^ MODPOW NEXT
1 18 FOR i 5 7 9 ^ MODPOW NEXT
>>
Takes 11 sec.
Michael
Hi Val,
thanks for the code. I had already read it in the problem forum for
problem #335. Impressive and quite concise. I really enjoyed reading
RPL in on the forum thread :)
Regards,
oliverue
I'm trying to understand your code but don't see things quite adding
up: The loop over 2 7 9 ^ MODPOW seems to produce a stack underrun
(assuming that MODPOW takes three args and returns one).
You're not using "i", is that intended?
Can you check your pasted code?
Can you also let me know the last 3 digits of the solution?
I'd like to code it up for 50g/ND1 (both of which won't need ALG48 for
this) but don't want to use the Project Euler website to check for the
correctness of the result.
(I do respect the achievement of solving those harder problems, and
that the solution thread is reserved for those, who actually solved
the problem...)
val
Hello !
Yes, the code shouldn't use a FOR i ... NEXT as i is not used.
Should be 1 18 START 2 7 9 ^ MODPOW NEXT instead.
The first argument is always on the stack, so you have a total of 3
arguments each time MODPOW is called.
The 3 last digits are 316.
val
>>
>> Can you check your pasted code?
>>
Oops ! You're right, the pasted code is wrong (missing minus sign on
line 2).
Here is the correct one :
P335:
<<
4 SBR 8 *
3 SBR 9 * -
2 SBR 24 * +
11 7 9 ^ MOD-
6 /
> >
SBR:
<<
1 18 START 2 7 9 ^ MODPOW NEXT
1 18 START 5 7 9 ^ MODPOW NEXT
> >
I wish project Euler had RPL as en entry in their listbox of
programming language ;)
oliverue
now.
Just for fun, here's your code in "GolfScript/MorphEngine":
7 9?:m
{{2 m modpow}18*{5 m modpow}18*}:sbr
4 sbr 8 *
3 sbr 9 * -
2 sbr 24 * +
11 - m mod 6 /
It could be written a little terser. It almost looks like your RPL
owing to the fact that we only have two loops as control structures
(and that GolfScript is a stack-based language, too).
Run-time: 0.2s
>I wish project Euler had RPL as en entry in their listbox of programming language ;)
Don't wish, but support my request on http://forum.projecteuler.net/viewtopic.php?f=49&t=2458
;-)
oliverue
7 9?:m;{2:i;{{i m modpow}18*5:i;}2*}:s;4s 8*3s 9*-2s 24*+11-m%6/
oliverue
surprisingly, was still open for solution posts. (#303, solved
yesterday, was closed.)
oliverue
MorphEngine and RPL calcs.
It's here: http://forums.naivedesign.com/viewtopic.php?f=7&t=270
Feel free to use the thread to register your solutions (not the code;
just PE problem number and run-time), and I'll update the list.
(There's another thread for PE code submissions:
http://forums.naivedesign.com/viewtopic.php?f=10&t=262)
The list is open to all RPL calcs. Hopefully you won't object to it
being hosted on my site, but since there's no white-board for RPL
calcs (other than this newsgroup, which isn't really suitable for a
live document), I didn't see another viable place.
It would be cool if Project Euler would be changed to accept language
designations on a per-submissions basis, so that this info would be
readily available from the right place. I requested that in my "please
add ME and RPL" request, but I doubt they'll go for that any time
soon.
Looking forward to your submissions. Will be interesting to see how
many of these places can (and cannot!) be solved on our little calcs.
(I suppose most--if not all--can, though I'm finding problems that
don't have super-elegant solutions, which can run in essentially no
time.)
oliverue
It doesn't appear on the statistics page yet, but is available from
the language pop-up.
oliverue
by user average?!
Congratulations, Arnaud, for having solved >200 problems! That's
pretty amazing.
I'm curious: what proportion of those have you solved on your HP?
How many of those (if you have that handy) actually run in under a
minute?
Arnaud Amiel
I have to admit to not having solved many at all on the hp... I am
still working hard on them but with a PC. I am now slowly revisiting
them on the hp. I will soon post here a small article which I hope
will be of interest but on problem 1. I am now working on problem 2
and I have problem 3 that is so easy on the hp that I would be ashamed
of posting an answer. Anyway, working in order.
Arnaud
Nemo
I solved 30 problems in UserRPL (using HPUserEdit) :
1..16,18..22,25,30,34,47,48,52,67,206,317,329
For example, prolem 8 : http://projecteuler.net/index.php?section=problems&id=8
and a user RPL solution :
«
"7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
1 1000 START
DUP HEAD STR-> SWAP TAIL
NEXT
DROP 1000 ->LIST
5 « * * * * » DOSUBS
« MAX » STREAM
»
oliverue
Thanks for your response. I would have been shocked (in a good way) if
you had done a sizable chunk of your solutions on an HP. Would
appreciate to hear how suitable your HP turns out to be in
(re-)solving these probs, as you get deeper into it.
For the first 6 probs, there're some really nice solutions for RPN
over at the hpmuseum, with no less than 7+ solutions for #1.
http://www.hpmuseum.org/cgi-sys/cgiwrap/hpmuseum/archv020.cgi?read=183803
Yes, I also see a 3-command solution for #3, but I would call this a
strength of the platform.
I did not survey the PE problems, or tried enough problems yet, to
have a feel for how solid a set of tools the built-in functions are,
for solving these problems.
Is your intended ARM asm project in any shape related to PE? (Maybe
you're in need of a fast prime sieve...)
Cheers.
oliverue
Thanks for mentioning which problems you have solved. Cool.
Your solution to #8 looks almost identical to mine.
In GS/ME: split{fromString}MAP 5{* * * *}DOSUBS{max}*
greenchile505
> For the first 6 probs, there're some really nice solutions for RPN
> over at the hpmuseum, with no less than 7+ solutions for #1.http://www.hpmuseum.org/cgi-sys/cgiwrap/hpmuseum/archv020.cgi?read=18...
There should probably be an "RPN" entry on the Project Euler website.
Then again, I don't know if folks at the museum are logging in and
posting their solutions on the official site. For some reason I doubt
it..
Arnaud Amiel
> Is your intended ARM asm project in any shape related to PE? (Maybe
> you're in need of a fast prime sieve...)
>
Basically, I have looked at PE1. You can solve it nearly instantly
using the solution everyone has already mentioned here.
However, nearly instantly takes 0.439s by implementing in RPL the pdf
you get once you solve the problem.
target: 999.
SumDivisibleBy: << target OVER / IP DUP 1. + * * 2. / IP >>
Euler1: << 3. SumDivisibleBy 5. SumDivisibleBy + 15. SumDivisibleBy -
>>
I thought to myself, in 0.439s I may be able to solve it by brute
force, that is divide every number to 999 by 3 and 5 and check the
remainder. So I did an implementation of the brute force algorithm in:
HP-Basic: 164.7073 s
This one took me a long time as I hadn't really use HP-Basic before.
<< 0.|>N;
FOR(I,1.,999.)
IF I MOD 3.==0.
THEN N+I|>N;
ELSE
IF I MOD 5.==0.
THEN N+I|>N;
END
END
NEXT ; RCL('N')
>>
RPL: 10.3606 s
<< 0. 1. 999.
FOR I
IF I 3. MOD 0. ==
THEN I +
ELSE
IF I 5. MOD 0. ==
THEN I +
END
END
NEXT
>>
SysRPL: 1.5356 s
!NO CODE
!RPL
::
CH0NOLASTWD
ZERO
1000
ONE_DO
INDEX@
THREE
#/
DROP
#0=ITE
::
INDEX@
#+
;
::
INDEX@
FIVE
#/
DROP
#0=
IT
::
INDEX@
#+
;
;
LOOP
UNCOERCE
;
@
Old style Saturn ASM: 0.1772 s
GOSBVL =SAVPTR
A=0 A
LA #999
B=A A
C=0 A
*BeginLoop
A=B A
R0=A A
R1=C A
LC(5) 3
GOSBVL =IntDiv
C=R0 A
B=C A
C=R1 A
?A#0 A
GOYES Test5
C=C+B A
GOTO EndTest
*Test5
A=B A
LC(5) 5
GOSBVL =IntDiv
C=R0 A
B=C A
C=R1 A
?A#0 A
GOYES EndTest
C=C+B A
*EndTest
B=B-1 A
GONC BeginLoop
R0=C A
GOSBVL =GETPTR
GOSBVL =PUSH#
LA(5) "UNCOERCE"
PC=(A)
@
New Saturn ASM: 0.449 s
SAVE
A=0.A
B=0.A
C=0.A
LC #999
D=C.A
{
C=D.A
LA 3
C%A.A
?C#0.A SKIPYES
{
C=D.A
B+C.A
}
SKELSE
{
C=D.A
LA 5
C%A.A
?C#0.A
{
C=D.A
B+C.A
}
}
D-1.A
UPNC
}
A=B.A
R0=A.A
LOAD
GOSBVL PUSH#
LA(5)"UNCOERCE"
PC=(A)
@
HPGCC2: 0.625 s
#include <hpgcc49.h>
int main()
{
int i,result=0;
sys_slowOff();
for(i=1;i<1000;i++)
if(i%3==0) result+=i;
else if (i%5==0) result+=i;
sat_push_real((float)result);
sys_slowOn();
return(0);
}
And it is still too slow. So my last chance is using ARM assembly but
at the moment my division routine locks up the calc...
Conclusion, in case we didn't know it from the start, by working on
your implementation you can really speed up the problem solving but
working on you algorithm is more effective.
Arnaud
oliverue
I'm amazed that old-style asm is faster than new-style (even though I
didn't know there was two flavors), that it's a whopping factor 100x
faster than User RPL and that it's 5x faster than HPGCC (which, as
only native ARM solution ought to have the upper hand, or so I'd have
thought).
Surprising, too, that the closed-form solution in User RPL takes half
a second. I wonder if a small variation of writing it could make it
much faster.
Here're my three implementation for #1:
RPL+ brute-force (0.53s):
≪ 0 =sum
1 999 FOR i
i 3 mod 0 ==
i 5 mod 0 ==
or
IF THEN sum i + =sum END
NEXT
sum
≫
RPL+ (0.021s):
≪ 1000 3 5 → n a b ≪
--n
a b lcm =c
n n a mod - =na
n n b mod - =nb
n n c mod - =nc
'(na*((na/a)+1) + nb*((nb/b)+1) - nc*((nc/c)+1) )/2' EVAL
≫≫
RPL (0.014s):
≪ 1000 → n '((n-1)*(((n-1)/3)+1)+(n-5)*(((n-5)/5)+1)-(n-10)*(((n-10)/
15)+1))/2' ≫
This last version is really a cheat, as it really relies on
intermediates (1,5,10) computed elsewhere.
(All timings for ND1.)
oliverue
JavaScript (0.004s):
function() { /*as is*/
var sum = 0;
for (var i = 0; i<1000; i++)
if (i%3 === 0 || i%5 === 0)
sum += i;
return sum;
}
(Note, the iPhone uses an ARM clocked ~10x faster than a 50g.)
Arnaud Amiel
> Thanks for sharing these results!
>
> I'm amazed that old-style asm is faster than new-style (even though I
> didn't know there was two flavors), that it's a whopping factor 100x
> faster than User RPL and that it's 5x faster than HPGCC (which, as
> only native ARM solution ought to have the upper hand, or so I'd have
> thought).
>
> Surprising, too, that the closed-form solution in User RPL takes half
> a second. I wonder if a small variation of writing it could make it
> much faster.
>
Sorry, rereading my post, I noticed I forgot some zeros. All 3 that
are surprisingly slow (Closed form RPL, new style Satrun and HPGCC2)
should be around 0.05s and not 0.5s.
The main difference in the old style ASM and new style is that in old
saturns there was no division instruction so I have to call the IntDiv
routine whereas the emulator in the hp50g does have a division
instruction which makes the solution much faster.
Arnaud Amiel
>
> Thanks for your response. I would have been shocked (in a good way) if
> you had done a sizable chunk of your solutions on an HP. Would
> appreciate to hear how suitable your HP turns out to be in
> (re-)solving these probs, as you get deeper into it.
>
As the problems progress, computing time or memory requirements
increase quite a lot which makes most of the problems unsuitable for a
calculator. There are still some from time to time that you can nearly
solve with just pen and paper.
Anyway, they usually take quite some time. I have just solved problem
21 in just under 50 min. in pure RPL. I am sure I can improve a little
bit but it is quite optimised already... most other problems will
surely take a few hours
Arnaud
Andreas Möller
some clarification:
> I'm amazed that old-style asm is faster than new-style (even
> though I didn't know there was two flavors)
> Old style Saturn ASM: 0.1772 s
> New Saturn ASM: 0.449 s
There is *NO* "Old style Saturn" and neither is there a "New Saturn
ASM".
Both are exactly the same in terms of the binaries they produce.
The difference is in the syntax used/allowed.
SASM = traditional Saturn Assembler syntax
MASD = Metakernel Saturn ML syntax
If you look at the provided source code example you see that the code
is *different* and that is the reason for the varying speeds
Both are available on the HP 50g directly whereas in debug4x MASD is
not exactly the same as it is on the calculator. For details consult
the help file of debug4x and/or the Metakernel documentation.
> HPGCC (which, as only native ARM solution
It is a C Cross-Compiler for the ARM based HP graphical calculators
(the ones that contain the "Saturnator").
Native ARM ML code can be coded on the calculator directly or with a
Cross-Compiler.
In debug4x you can include ARM ML as binaries into your sources.
> there was no division instruction
Yes, as the physical Saturn Chip can not do this (same as the
instructions D=A f and D=B f etc.). If you use this, than your program
won’t work in EMU49 or on a real HP 49G, for example.
This is, of course, true for *all* ARM system instructions / ARM
enhancement instructions.
Details about this can be found in "Introduction to Saturn Assembly
Language" available at hpcalc.org
HTH,
Andreas
http://www.software49g.gmxhome.de
Arnaud Amiel
wrote:
> Hello,
> There is *NO* "Old style Saturn" and neither is there a "New Saturn
> ASM".
Yes, that is correct, I just wanted to show 2 different "grammars" one
with labels and one with skips. Of course, as I pointed out later, the
speed difference is that in what I call "new style", I use the %
instruction instead of the IntDiv subroutine. That would not work on
old calculators but does speed things a lot on the newer ones.
Arnaud
Andreas Möller
communication *is* a lot easier, if for well known terms these will be
used instead of introducing *new* ones :-)
Avoids confusion of "the elder sages" and allows the "apprentice" to
learn the correct terms.
Regards,
Andreas
http://www.software49g.gmxhome.de
Nemo
Hi
It tooks 0,49 sec with HPPascal on a 50G :
Var i,t : Integer;
Begin
For i:=1 to 999 Do
If i mod 3=0 Or i mod 5=0 Then t:=t+i;
End.
Strange that the old HPPascal wich generate SATURN code is faster than
HPGCC
Arnaud I think your C Code could perhaps be faster with an "Or"
sequence instead of two imbricated IF
Nemo
>
> RPL (0.014s):
> ≪ 1000 → n '((n-1)*(((n-1)/3)+1)+(n-5)*(((n-5)/5)+1)-(n-10)*(((n-10)/
> 15)+1))/2' ≫
>
> This last version is really a cheat, as it really relies on
> intermediates (1,5,10) computed elsewhere.
>
> (All timings for ND1.)
You can improve this :
'((n-1)*(((n-1)/3)+1)+(n-5)*(((n-5)/5)+1)-(n-10)*(((n-10)/15)+1))/2'
EVAL
give
'(7.n^2-5.n+40)/30'
After that, it is impossible to calculate speed on 50G because it's
less than a TICK (1/8192sec)
Arnaud Amiel
Arnaud