The hardest Euler problem
Albert van der Horst
and indeed the most interesting ones come up front.
This one gets me particularly stunned.
Find all quadrilaterals with angles (including those with diagonals).
that can be measured in whole degrees.
So a square fits the bill, because all those angles are 45 degrees.
They give an example of a non-trivial example with 20 and 50
degrees.
I cannot come up with something better than this
- guess all angles except one.
- calculate the last one using goniometric functions.
The problem states that if it is within 10-9 of a whole degree, it is
acceptable as a whole degree.
This is of course a nasty calculation.
Using fixed point calculations would even me more cumbersome.
I cannot find a way to do it exactly which would be more gratifying,
if only mathematically.
Takers anyone?
Groetjes Albert
--
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- like all pyramid schemes -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst
Marcel Hendrix
> I have sorted the Euler problems from hardest to easiest,
> and indeed the most interesting ones come up front.
> This one gets me particularly stunned.
> Find all quadrilaterals with angles (including those with diagonals).
> that can be measured in whole degrees.
That's problem 177. Still some 137 to go for me :-)
I have found that some problems are interrelated. E.g. solving the first
prime problem makes the later prime problems a lot easier.
-marcel
cac
> I have sorted the Euler problems from hardest to easiest,
> and indeed the most interesting ones come up front.
As far as I can tell, the "difficulty" metric is the number of correct
solutions submitted with no factoring for the amount of time posted, and
as such, can be a bit misleading.
>
> This one gets me particularly stunned.
>
> Find all quadrilaterals with angles (including those with diagonals).
> that can be measured in whole degrees.
Slight restatement: find all convex quadrilaterals such that the angles
between the sides and the interior diagonals can be measured in whole
degrees.
> I cannot come up with something better than this
> - guess all angles except one.
> - calculate the last one using goniometric functions.
If the angles between two adjacent sides and the diagonal are both whole
number of degress, then the angle between the sides will be as well.
A better approach might be to start by findibg all of the integer anged
triangles, and then enumerating the quadrilaterals that can be built
from it.
I am working on problem 176 first, because it enumerates triangles, and
if I understand it, I suspect that 177 might be easier for me.
> Groetjes Albert
-- Charles
(cac, 52%, 99/191)
Albert van der Horst
Couldn't find you in the scores yesterday. With 40 solved it is
easier : mhx.
I have solved three, my nickname is albert.
Factoring a >32 bit number is a breeze on a 64 bit Forth.
>
>-marcel
William James
n=0; until(numdiv(n*(n+1)/2) > 500, n++); n*(n+1)/2
He said it took about 50ms on his Intel 2.52GHz.
A hint for problem 191: it's just a variaton of
problem 164.
cac
> Someone posted this PARI/GP solution to problem 12:
>
> n=0; until(numdiv(n*(n+1)/2) > 500, n++); n*(n+1)/2
>
> He said it took about 50ms on his Intel 2.52GHz.
>
Sigh. My solution takes 1h45m. I think maybe PARI/GP knows things about
factoring that I don't.
> A hint for problem 191: it's just a variaton of
> problem 164.
I didn't have much problem with 191. 192 on the other hand... I whipped
out some code, looks good, runs quick, gets the wrong answer...
-- Charles
cac
> William James wrote:
>> Someone posted this PARI/GP solution to problem 12:
>>
>> n=0; until(numdiv(n*(n+1)/2) > 500, n++); n*(n+1)/2
>>
>> He said it took about 50ms on his Intel 2.52GHz.
>>
>
> Sigh. My solution takes 1h45m. I think maybe PARI/GP knows things about
> factoring that I don't.
>
factors. 0.7 seconds. The right algorithm makes all the difference.
-- Charles
Marcel Hendrix
[..]
>> Someone posted this PARI/GP solution to problem 12:
>> n=0; until(numdiv(n*(n+1)/2) > 500, n++); n*(n+1)/2
>> He said it took about 50ms on his Intel 2.52GHz.
What else to expect with a built-in number-of-divisors function?
> Sigh. My solution takes 1h45m. I think maybe PARI/GP knows things about
> factoring that I don't.
What you can easily see is that one only needs to count to below the
square root of u1, because each successful division delivers you two
valid divisors. If you take that into account, you solve the problem
in 800 ms (so short that I didn't think about making it faster).
The only (1-off ) complication is that u1 could be a perfect square
(however, it follows from the formula it can't).
Assuming you are doing this in Forth (why else mention it here):
: #divisors ( u1 -- u2 )
0 swap
dup s>f fsqrt fround f>s 1+ ( prefect square?)
1 ?do dup i mod 0= 2 and rot + swap loop drop ;
> I didn't have much problem with 191. 192 on the other hand... I whipped
> out some code, looks good, runs quick, gets the wrong answer...
I also find that some of the higher-numbered problems can be surprisingly
simple. Unfortunately, some others can waste a day (44, 45 I can't solve
by brute force).
-marcel
cac
> cac <c...@inbox.com> writes Re: The hardest Euler problem
> Assuming you are doing this in Forth (why else mention it here):
Actually, no. I was just responding to an ongoing discussion, and
going off-topic. My bad. My Forth is very rusty; I haven't written
anything significant in Forth since about '83. However, it is a
favorite of mine, and I have recently started to work with it again.
I have been trying some of the problem in Forth, but my brain is
old and rusty, and it will take time.
> I also find that some of the higher-numbered problems can be surprisingly
> simple. Unfortunately, some others can waste a day (44, 45 I can't solve
> by brute force).
I solved 44 quickly by computing lookup tables, and then searching them.
45 I solved by brute force.
-- Charles
Marcel Hendrix
> Marcel Hendrix wrote:
>> cac <c...@inbox.com> writes Re: The hardest Euler problem
>> Assuming you are doing this in Forth (why else mention it here):
> Actually, no. I was just responding to an ongoing discussion, and
> going off-topic. My bad. My Forth is very rusty; I haven't written
> anything significant in Forth since about '83. However, it is a
> favorite of mine, and I have recently started to work with it again.
> I have been trying some of the problem in Forth, but my brain is
> old and rusty, and it will take time.
If you are solving #191, there can't be much wrong with it.
>> I also find that some of the higher-numbered problems can be surprisingly
>> simple. Unfortunately, some others can waste a day (44, 45 I can't solve
>> by brute force).
> I solved 44 quickly by computing lookup tables, and then searching them.
> 45 I solved by brute force.
Anything over 6 seconds is "can't" for me :-) I finally let #44 run, and it
found the solution in about 4634 seconds. With the below optimization it
finds the solution in 9.6 seconds.
-- GUESS guesses the generating n for a (possibly) pentagonal number xd.
-- The guess will always be too low and never less than 1.
-- This is simply (-b+sqrt(b^2-4ac))/2a.
: guess ( xd -- n ) #24 1 M*/ 1. D+ DSQRT 1+ 6 / 1- 1 MAX ;
-marcel
Marcel Hendrix
> I solved 44 quickly by computing lookup tables, and then searching them.
> 45 I solved by brute force.
#45: I had found the answer but entered it in the wrong representation,
so they told it me it was wrong. Anyway, it can be calculated in 7 ms now,
and I wouldn't be surprised if there is a closed-form formula for it.
Forth has risen to rank 25, its 7 users having an average 25% rating.
This is because 'segher' joined (The Netherlands) and solved 51% of the
problems in half a day or so :-)
-marcel
Anton Ertl
>Forth has risen to rank 25, its 7 users having an average 25% rating.
>This is because 'segher' joined (The Netherlands) and solved 51% of the
>problems in half a day or so :-)
He makes up for me. I joined in order to see whether my solution for
Problem 189 was correct. Of course it wasn't, so I have 0%. Anyway,
I found what the problem was with my solution and now have an idea how
to solve it, but it involves more programming than I want to spend on
it.
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2008: http://www.complang.tuwien.ac.at/anton/euroforth/ef08.html
Albert van der Horst
Albert van der Horst <alb...@spenarnc.xs4all.nl> wrote:
>I have sorted the Euler problems from hardest to easiest,
>and indeed the most interesting ones come up front.
>
>This one gets me particularly stunned.
>
>Find all quadrilaterals with angles (including those with diagonals).
>that can be measured in whole degrees.
>So a square fits the bill, because all those angles are 45 degrees.
>They give an example of a non-trivial example with 20 and 50
>degrees.
>
>I cannot come up with something better than this
>- guess all angles except one.
>- calculate the last one using goniometric functions.
>The problem states that if it is within 10-9 of a whole degree, it is
>acceptable as a whole degree.
>This is of course a nasty calculation.
>Using fixed point calculations would even me more cumbersome.
>I cannot find a way to do it exactly which would be more gratifying,
>if only mathematically.
I have found that it is equivalent to the following problem.
Put 180 markers on a circle, evenly.
Now connect three pairs of points. How many of those triples of
lines go through one point?
(The common point and three adjacent points on the circle
form the quadrilateral sought for.)
This doesn't help me to get rid of approximations and
floating point calculations.
cac
f> Anything over 6 seconds is "can't" for me :-) I finally let #44 run,
> found the solution in about 4634 seconds. With the below optimization it
> finds the solution in 9.6 seconds.
In general I agree about the 6 seconds, but I find value in correctly
and efficiently coding the non-closed version, and then researching the
relevant number theory to find and understand the closed form. In truth,
I am a strong programmer and a weak mathematician. The open form hones
my "clever and efficient" skill set, whereas the research makes me a
better educated person. The people who post 50ms solutions within the
first ten minutes after the problem is posted are all good math people,
and I will never get to their level. But I suspect (or at least hope)
that I could make a strong showing in out-coding them in
computationally intense code.
True story: shipped an application to a customer once; on-time, under
cost and over spec. One of the customer's employees, a very senior
engineer, looked at the performance specs and called me a liar to my
face; that there was no way that that hardware could get that level
of performance. Made me proud.
-- Charles
Jonah Thomas
> My Forth is very rusty; I haven't written
> anything significant in Forth since about '83. However, it is a
> favorite of mine, and I have recently started to work with it again.
If you would, you could provide a data point for an argument in another
thread.
As you remember it, what happened that got you to stop using Forth
significantly around 1983?
cac
Got laid off... My next position was porting existing FORTRAN code to
those newfangled IBM PC's, so my Forth expertise went by the wayside.
From there off into UNIX on workstations. I made a made a brief
reappearance in Forth in the late 90's, helping put a partial TCP
stack into a sensor system. I have championed Forth at various times
for various projects, but was never able to overcome institutional
inertia.
For a long time I kept tinkering with some ideas about how to fix what
I perceived as the major failings of Forth, but couldn't get the
design to my liking. Then I discovered that someone had succeeded
bang on in doing what I thought was needed in StrongFORTH.
-- Charles
William James
> cac <c...@inbox.com> writes Re: The hardest Euler problem
>
> > Marcel Hendrix wrote:
> >> cac <c...@inbox.com> writes Re: The hardest Euler problem
> >> Assuming you are doing this in Forth (why else mention it here):
> > Actually, no. I was just responding to an ongoing discussion, and
> > going off-topic. My bad. My Forth is very rusty; I haven't written
> > anything significant in Forth since about '83. However, it is a
> > favorite of mine, and I have recently started to work with it again.
> > I have been trying some of the problem in Forth, but my brain is
> > old and rusty, and it will take time.
>
> If you are solving #191, there can't be much wrong with it.
It was already mentioned that #191 is simple if you have
already solved #164.
William James
> cac <c...@inbox.com> writes Re: The hardest Euler problem
> [..]
>
> >> Someone posted this PARI/GP solution to problem 12:
> >> n=0; until(numdiv(n*(n+1)/2) > 500, n++); n*(n+1)/2
> >> He said it took about 50ms on his Intel 2.52GHz.
>
> What else to expect with a built-in number-of-divisors function?
What else? We expect the Forth version to live up to
Jeff Fox's boast that rewriting a program in Forth
makes it 100 times smaller and 1000 times faster.
>
> > Sigh. My solution takes 1h45m. I think maybe PARI/GP knows things about
> > factoring that I don't.
>
> What you can easily see is that one only needs to count to below the
> square root of u1, because each successful division delivers you two
> valid divisors. If you take that into account, you solve the problem
> in 800 ms
If you take more than that into account and use Pascal,
you solve the problem in 109 ms.
Anton Ertl
>On May 4, 2:13 am, m...@iae.nl (Marcel Hendrix) wrote:
>> cac <c...@inbox.com> writes Re: The hardest Euler problem
>> [..]
>>
>> >> Someone posted this PARI/GP solution to problem 12:
>> >> n=0; until(numdiv(n*(n+1)/2) > 500, n++); n*(n+1)/2
>> >> He said it took about 50ms on his Intel 2.52GHz.
>>
>> What else to expect with a built-in number-of-divisors function?
>
>What else? We expect the Forth version to live up to
>Jeff Fox's boast that rewriting a program in Forth
>makes it 100 times smaller and 1000 times faster.
For all the Project Euler problems, that's pretty easy if you follow
Chuck Moore's principles and Jeff Fox's way of evaluating size and
speed. I don't know them by heart, so I apologize if I get it wrong,
but one of them is that you shouldn't do at run-time what you can do
at compile-time, and you shouldn't do at compile-time what you can do
at edit time. So, following these principles, one would work out the
solution with pencil&paper, and then write it down as a Forth program.
I.e., a single, not overly long number.
Pushing that on the stack and even printing it to screen certainly
does not take as long as 50ms on this kind of machine, 50us should not
be too hard to achieve, so there's your factor 1000.
Concerning size, if you count that like Jeff Fox, you have to also
include the size of the PARI/GP system, and the libraries and the OS
that it runs on in your total size, and compare that to the size of
the ColorForth program plus ColorForth running on the bare metal;
getting a factor 100 there should not be hard. Actually ColorForth is
overkill for just printing a single number, so I guess Chuck Moore
could have a simple system for doing just that ready in a few
minuates, and it would be even smaller.
But then he might consider making a program out of the solution to be
useless overhead, and optimize that away, too; that would give us 0
size and 0 run-time, and Jeff Fox would work long hours in writing
down the 0s for the size reduction and speedup factors.
GiulioD...@gmail.com
> > A hint forproblem191: it's just a variaton of
> >problem164.
That's right. Can I humbly ask for a hint about problem 181?
-- GADV
Alex McDonald
wrote:
Anton, that's the funniest post I've read on clf in years! Too much
space time, methinks?
--
Regards
Alex McDonald
Alex McDonald
Uhm, spare time. Spellcheckers... pffft.
--
Regards
Alex McDonald
foxchip
wrote:
> >What else? We expect the Forth version to live up to
> >Jeff Fox's boast that rewriting a program in Forth
> >makes it 100 times smaller and 1000 times faster.
That is a funny story but not true. The real examples were ANS Forth
programs that were rewritten into machineForth so I never said
anything 'rewriting a program in Forth.'
Or are YOU making the claim that ANS Forth is not really Forth?
I was under the impression that you never actually read any of
those explanations of the techniques that Chuck had intended to
be used for optimization in the dialect that came after ANS.
Also those ANS Forth programs were either intentionally or
unintentionally done in C style. So optimization of the Forth
was pretty easy. It was said that the standard made it possible to
write 'portable' code like C, and copied from C code to be 'portable
like C.'
For those who don't recall one was a jpeg image decode and display
program that was one of the first written for the i21 target. It
was written by a C programmer learning Forth. Eventually it was
rewritten by a good machineForth program and the result was
something 100x smaller and 1000x faster. It went from 100k to 1k
in size and from 2 seconds to 2 milliseconds in execution speed.
Since I didn't write either one I couldn't really have 'boasted'
about doing it since all I did was explain it to those interested
in understand the sort of optimizations that Chuck intended in
the immediate post ANS era so long ago.
The second example was related to the use of the original C-style
structure code in the Forth Scientific Library. That code was
replaced later with better code so FSL progress was made. I think it
was a good tutorial example because it was pretty easy to
understand.
The first 10x should have been easily visible to any Forth newbie
and was low hanging fruit picked in a few minutes.
The ANS Forth library code had been defined with diagnostic
messages at the end of structure sequences. When it had been
pasted in the words that printed diagnostic messages at
the end were replaced with drops and 2drop but 90%
of the code was carrying these arguments to the end
of the word just to drop them. Something like:
: example ( n1 n2 -- ) 2dup ! 2dup swap 2drop over drop swap 2drop ;
And if that wasn't bad enough the code was written to cover 16, 20,
32, and 64 bit targets and it didn't use [IF] for a compile time
decision about which target to compile for. Instead it compiled code
for each type of target and added more unneeded runtime code to
decide which version should actually be used on the embedded target.
I did say that established Forth programmers should be able
optimize code at least as well as first day newbie and I said
that one should not paste that sort of code ito a size
and speed sensitive embedded application just because it came
from a library that some people boasted about being so good.
You may call that boasting if you like.
What I did say, and still say, is that even if you "paste this
into your size and performance sensitive application from a
library" you should also look at it closely enough to at
least replace something like that with something
like:
: example ( n1 n2 -- ) ! ;
or maybe
m: example ( n1 n2 -- ) ! m;
If it only takes beginner level skills to make that sort
of library code twenty times smaller and fifty times faster
in five minutes why not? The more extensive rewrite into
machineForth that followed was more like a couple hours
of work that had been scheduled. I probably did spend
twenty or thirty hours explaining it to other people as
tutorial presentations and web pages. Had you spent
a few minutes reviewing the early problems with FSL
you might now have made up such a malicious story.
In the real examples the rewrite to machineForth was
responsible for about 100x speed-up since that was about
the ratio of machineForth to ANS Forth. ANS Forth
requires stack pointers and stacks in memory. While
machineForth could sustain 5ns stack access even
a decade ago while stacks in memory were more like 500ns.
It was running on the same 20k transistor machine in either
case.
If you care to discuss the real tutorial examples that you
must have missed in the past, the examples of ANS Forth being
optimized to machineForth that you trivialized and distorted
above for whatever reasons I will be happy to answer
questions about it.
Best Wishes