Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #10644 > unrolled thread

Euler problem 303

Back to article view | Back to comp.lang.forth

Contents

  Euler problem 303 anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-03-30 15:02 +0000
    Re: Euler problem 303 Paul Rubin <no.email@nospam.invalid> - 2012-03-30 22:30 -0700
      Re: Euler problem 303 anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-03-31 13:08 +0000
        Re: Euler problem 303 Paul Rubin <no.email@nospam.invalid> - 2012-04-01 00:51 -0700
          Re: Euler problem 303 Paul Rubin <no.email@nospam.invalid> - 2012-04-01 01:46 -0700
            Re: Euler problem 303 mhx@iae.nl (Marcel Hendrix) - 2012-04-01 12:00 +0200
              Re: Euler problem 303 Paul Rubin <no.email@nospam.invalid> - 2012-04-01 12:57 -0700
                Re: Euler problem 303 Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-04-01 23:34 +0000
                  Re: Euler problem 303 Paul Rubin <no.email@nospam.invalid> - 2012-04-01 17:19 -0700
            Re: Euler problem 303 anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-02 10:53 +0000
    Re: Euler problem 303 Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-03-31 11:41 +0000
      Re: Euler problem 303 anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-03-31 13:30 +0000
        Re: Euler problem 303 Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-03-31 18:27 +0000

#10644 — Euler problem 303

Project Euler has lifted the thread length limit, so I did another
problem:

<http://projecteuler.net/problem=303>

If you want to participate, you have to work out the solution
yourself, otherwise you find my solution at

http://theforth.net/projects/euler303

The interesting thing here is that for the given problem size and
using the approach I have taken, I needed double-cell numbers and
mixed division on a 64-bit system: a 20-digit number (>64 bits) is
divided by a 4-digit number, with a 16-digit quotient (=< 64 bits).
In the Project Euler Forum lots of solutions were posted that were
similar to mine, but used a hand-derived special case to avoid
exceeding 64-bit numbers; the special case also avoids most of the
run-time.

One other interesting thing is that it generates (decimal) numbers
containing only 0, 1, 2 by converting numbers into strings using base
3, then converting the strings to numbers using base 10.  That makes
for a small program, but is slow, and I guess that most of the time is
spent in the conversion to the string.  I believe that it is possible
to generate these numbers significantly faster, but that would take
more code.

- 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 2011: http://www.euroforth.org/ef11/

[toc] | [next] | [standalone]

#10658

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> One other interesting thing is that it generates (decimal) numbers
> containing only 0, 1, 2 by converting numbers into strings using base
> 3, then converting the strings to numbers using base 10.  

    : tn ( n -- n ) 3 /mod dup if recurse 10 * + else drop then ;
    : test ( n -- ) 0 do i tn . loop ;
    50 test

works for me.  I'm still thinking about the rest of the problem.

[toc] | [prev] | [next] | [standalone]

#10665

Paul Rubin <no.email@nospam.invalid> writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> One other interesting thing is that it generates (decimal) numbers
>> containing only 0, 1, 2 by converting numbers into strings using base
>> 3, then converting the strings to numbers using base 10.  
>
>    : tn ( n -- n ) 3 /mod dup if recurse 10 * + else drop then ;

: desired-form ( u1 -- ud2 )
    \ u2 is the u1th cool number
    3 base ! 0 <# #s #>
    decimal 0 0 2swap >number 2drop ;

The same basic functionality, but produces doubles (which are needed);
it's probably also significantly slower, mainly because it also works
with doubles in the #S part, where it is not necessary (for this problem).

- 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 2011: http://www.euroforth.org/ef11/

[toc] | [prev] | [next] | [standalone]

#10682

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> The same basic functionality, but produces doubles (which are needed);

I think with 64 bit cells, it should be possible to do this problem
without doubles.  My solution is <s>too small to fit in the margin</s>
still under development but the basic idea is to do most of the
arithmetic mod n, where is the number (< 10000) that you're trying to
solve.

[toc] | [prev] | [next] | [standalone]

#10683

Paul Rubin <no.email@nospam.invalid> writes:
> I think with 64 bit cells, it should be possible to do this problem
> without doubles.  

Hmm, my program had a bug, these numbers get bigger than I thought.  Do
you get 11112222222222222222 for f(9999)?  That is approx 2**63.26.

[toc] | [prev] | [next] | [standalone]

#10684

Paul Rubin <no.email@nospam.invalid> writes Re: Euler problem 303

> Paul Rubin <no.email@nospam.invalid> writes:
>> I think with 64 bit cells, it should be possible to do this problem
>> without doubles.  

> Hmm, my program had a bug, these numbers get bigger than I thought.  Do
> you get 11112222222222222222 for f(9999)?  That is approx 2**63.26.

$9A368B3C6CC1E38E

-marcel

[toc] | [prev] | [next] | [standalone]

#10690

mhx@iae.nl (Marcel Hendrix) writes:
>> Hmm, my program had a bug, these numbers get bigger than I thought.  Do
>> you get 11112222222222222222 for f(9999)?  That is approx 2**63.26.
>
> $9A368B3C6CC1E38E

Thanks.  I get 1111981904675169 ($3f357766cc161) as my final answer.  My
Haskell program runs in 16 seconds and uses around 100k of memoized data
of which about 80% could be eliminated, slowing down the program by a
small constant factor.  I'll try for a Forth version, which should be a
bit faster by using 64-bit arithmetic carefully (the Haskell program
uses bignums).  This is cheating slightly since the bignum calculation
is how I know that the 64-bit numbers don't overflow.

[toc] | [prev] | [next] | [standalone]

#10692

In article <7xehs7uswf.fsf@ruckus.brouhaha.com>,
Paul Rubin  <no.email@nospam.invalid> wrote:
>mhx@iae.nl (Marcel Hendrix) writes:
>>> Hmm, my program had a bug, these numbers get bigger than I thought.  Do
>>> you get 11112222222222222222 for f(9999)?  That is approx 2**63.26.
>>
>> $9A368B3C6CC1E38E
>
>Thanks.  I get 1111981904675169 ($3f357766cc161) as my final answer.  My
>Haskell program runs in 16 seconds and uses around 100k of memoized data
>of which about 80% could be eliminated, slowing down the program by a
>small constant factor.  I'll try for a Forth version, which should be a
>bit faster by using 64-bit arithmetic carefully (the Haskell program
>uses bignums).  This is cheating slightly since the bignum calculation
>is how I know that the 64-bit numbers don't overflow.

Have you checked the correctness of your answer with http://projecteuler.net ?

P.S. You're not supposed to publish answers, in order not to spoil
the fun for the rest of us.

Groetjes Albert

--
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#10694

Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
> Have you checked the correctness of your answer with http://projecteuler.net ?

No, I was hoping you or Marcel or Anton would say whether my answer was
right.

> P.S. You're not supposed to publish answers, in order not to spoil
> the fun for the rest of us.

Well, I figured that the spoiler is the algorithm, and that the number
itself doesn't give much away (assuming even that it's the right
number).  However, maybe I shouldn't have stated the running time and
memory footprint.

[toc] | [prev] | [next] | [standalone]

#10707

Paul Rubin <no.email@nospam.invalid> writes:
>Hmm, my program had a bug, these numbers get bigger than I thought.  Do
>you get 11112222222222222222 for f(9999)?  That is approx 2**63.26.

Indeed.  I had thought that only 18 digit numbers fit in 64 bits, but
I was wrong (also, my first version that used /MOD gave a negative
result).  The limit is 1.84E19 (i.e., a 20-digit number) for unsigned
numbers.

- 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 2011: http://www.euroforth.org/ef11/

[toc] | [prev] | [next] | [standalone]

#10664

In article <2012Mar30.170245@mips.complang.tuwien.ac.at>,
Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>Project Euler has lifted the thread length limit, so I did another
>problem:
>
><http://projecteuler.net/problem=303>

If you do a fairly recent problem (like a half year)
chances are slim that there are already 100 posts
in the forum anyway. The first 100 are kept for eternity.
I have checked a couple of the problems of the last year.
One in ten of the solvers do a write up. So if you solve
a problem with less than 1000 solvers up to date, you are
likely to be one of the first 100 publishers.

>
>If you want to participate, you have to work out the solution
>yourself, otherwise you find my solution at
>
>http://theforth.net/projects/euler303
>
>The interesting thing here is that for the given problem size and
>using the approach I have taken, I needed double-cell numbers and
>mixed division on a 64-bit system: a 20-digit number (>64 bits) is
>divided by a 4-digit number, with a 16-digit quotient (=< 64 bits).
>In the Project Euler Forum lots of solutions were posted that were
>similar to mine, but used a hand-derived special case to avoid
>exceeding 64-bit numbers; the special case also avoids most of the
>run-time.

I came across several situation in Euler problems where 64 bit
doubles came in handy. OTOH half of my Java solutions had
overflow problems, which is nasty because you expect that language
to be safe. I don't remember overflow much to this particular
problem, though.

>
>One other interesting thing is that it generates (decimal) numbers
>containing only 0, 1, 2 by converting numbers into strings using base
>3, then converting the strings to numbers using base 10.  That makes
>for a small program, but is slow, and I guess that most of the time is
>spent in the conversion to the string.  I believe that it is possible
>to generate these numbers significantly faster, but that would take
>more code.

My solution is not much faster and requires a few gigabytes of
dictionary space.

I recommend the problem. It is not overly hard, like the infamous
177 that I still not have solved. There is one Forther who has solved
300+ problems now, but I need some help to make Forth look good.

>
>- anton

Groetjes Albert

--
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#10668

Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>In article <2012Mar30.170245@mips.complang.tuwien.ac.at>,
>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>Project Euler has lifted the thread length limit, so I did another
>>problem:
>>
>><http://projecteuler.net/problem=303>
>
>If you do a fairly recent problem (like a half year)
>chances are slim that there are already 100 posts
>in the forum anyway. The first 100 are kept for eternity.
>I have checked a couple of the problems of the last year.
>One in ten of the solvers do a write up. So if you solve
>a problem with less than 1000 solvers up to date, you are
>likely to be one of the first 100 publishers.

Maybe.  Still, the thread length limit dampened my enthusiasm enough
that I did not take on any more problems.  After all, one should not
discuss the solution elsewhere, one could not discuss the solution
there; that was not very attractive.

> I don't remember overflow much to this particular
>problem, though.

No, you used a completely different approach.  However, given that
f(9999) does not fit in 64 bits, a straightforward solution will have
that problem.

- 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 2011: http://www.euroforth.org/ef11/

[toc] | [prev] | [next] | [standalone]

#10672

In article <2012Mar31.153037@mips.complang.tuwien.ac.at>,
Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>>In article <2012Mar30.170245@mips.complang.tuwien.ac.at>,
>>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>>Project Euler has lifted the thread length limit, so I did another
>>>problem:
>>>
>>><http://projecteuler.net/problem=303>
>>
<SNIP>
>
>> I don't remember overflow much to this particular
>>problem, though.
>
>No, you used a completely different approach.  However, given that
>f(9999) does not fit in 64 bits, a straightforward solution will have
>that problem.

I looked again into the problem.
My solution indeed handles 9999 as a special case too.
And it takes about 30 seconds on gforth.

>
>- 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 2011: http://www.euroforth.org/ef11/


--
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.forth

csiph-web