Re: 8 queens problem in Oforth

From	Paul Rubin <no.email@nospam.invalid>
Newsgroups	comp.lang.forth
Subject	Re: 8 queens problem in Oforth
Date	2015-03-23 16:14 -0700
Organization	A noiseless patient Spider
Message-ID	<87twxb71do.fsf@jester.gateway.sonic.net> (permalink)
References	(16 earlier) <menqmi$q1t$1@dont-email.me> <87lhio8iai.fsf@jester.gateway.sonic.net> <mepcfl$m0l$1@dont-email.me> <87619r8hw1.fsf@jester.gateway.sonic.net> <meq56o$3ir$1@dont-email.me>

Show all headers | View raw

Bernd Paysan <bernd.paysan@gmx.de> writes:
>> Right, not that great for creating lots of them on the fly, since they
>> aren't gc'd.
> You can use marker/forget to explicitely free the memory after use.

That only works if no other stuff is created the same way during the
computation, that needs to be kept around.  This is why GC was invented.

> I don't understand why you don't get it, even though you see my examples: 
> Forth *has* higher-order features.  Fortran doesn't.

I think you can pass something like xt's in Fortran, i.e. you can pass
the name of a function as a parameter, similarly to in C.  I'm not sure
how that's different from Forth's xt-passing style.  What's missing is
"compile," which makes a new callable, but it's still not on an equal
footing with other values like integers, since it consumes memory every
time you make one, that has to be freed manually.  (OK, I guess using
marker/forget for functions is like using the data stack for numbers,
but it seems easier for words to interfere).
>
> What it doesn't have (usually) is GC.  If you really want to allocate
> many, many functions, and not run out of space, you need some more
> explicit memory management in Forth.

Ok, fair enough.

> Though I'm not at all sure that this integration approach is "more
> natural".  After all, this approach requires to compute f() two times
> on each point of the approximated curve.

The integration routine in the Hughes paper?  I don't think it does that
except in the first illustrative example.  See the middle of page 14:

    "Also, (f mid) is evaluated in each recursive call. It is therefore
    preferable to use the following version which never recomputes a
    value of f."

> The classical thing is that when two points aren't sufficient, you do
> more points, and then have (f(x0)/2 + f(x1) + f(x2) +++
> f(xn)/2)*(xn-x0)/n.

That's considerably worse than what the paper does.  The paper's method
amounts to using higher and higher derivatives of the function as you
add more points instead of throwing that info away.  So with two points
you have the trapezoid method (linear approximation of the function);
then you add a third point and instead of a piecewise linear
approximation you get a quadratic approximation (equivalent to Simpson's
rule); then with more points you get even higher order approximations.
I haven't checked carefully but I think this may be equivalent to
Richardson extrapolation: basically you do a polynomial fit to the
sequence of approximations you've done, then extrapolate to find the
polynomial's value if the integration step size is zero.  That
(Romberg's method) is much better than the trapezoid rule, Simpson's
rule, etc.

> And then the numerical integral is just an ordinary higher order
> function.  You still can create a compiled version of it in Forth to
> be more speed efficient.  Typically, you would do so at compile time,
> not at run time.

Yes, for sure, these methods were well-known in numerical analysis long
before Scheme was invented and maybe before computers.  There are plenty
of Fortran implementations and maybe some Forth ones.  It's just
conceptually clearer (at least debatably) to write them the way the
Hughes paper does.

Thread

8 queens problem in Oforth "WJ" <w_a_x_man@yahoo.com> - 2015-03-19 07:53 +0000
  Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-19 08:58 -0700
    Re: 8 queens problem in Oforth Doug Hoffman <glidedog@gmail.com> - 2015-03-20 08:16 -0400
      Re: 8 queens problem in Oforth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-03-21 10:11 +0000
        Re: 8 queens problem in Oforth franck.bensusan@gmail.com - 2015-03-21 03:45 -0700
          Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-21 14:14 -0700
            Re: 8 queens problem in Oforth franck.bensusan@gmail.com - 2015-03-21 14:28 -0700
              Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-21 14:38 -0700
                Re: 8 queens problem in Oforth franck.bensusan@gmail.com - 2015-03-21 15:15 -0700
                Re: 8 queens problem in Oforth hughaguilar96@gmail.com - 2015-03-21 18:23 -0700
                Re: 8 queens problem in Oforth franck.bensusan@gmail.com - 2015-03-22 03:03 -0700
                Re: 8 queens problem in Oforth hughaguilar96@gmail.com - 2015-03-22 14:04 -0700
                Re: 8 queens problem in Oforth franck.bensusan@gmail.com - 2015-03-22 16:34 -0700
                Re: 8 queens problem in Oforth hughaguilar96@gmail.com - 2015-03-22 21:49 -0700
                Re: 8 queens problem in Oforth Raimond Dragomir <raimond.dragomir@gmail.com> - 2015-03-23 00:05 -0700
                Re: 8 queens problem in Oforth hughaguilar96@gmail.com - 2015-03-23 21:43 -0700
                Re: 8 queens problem in Oforth franck.bensusan@gmail.com - 2015-03-24 04:13 -0700
                Re: 8 queens problem in Oforth franck.bensusan@gmail.com - 2015-03-23 00:17 -0700
                Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-21 19:47 -0700
                Re: 8 queens problem in Oforth franck.bensusan@gmail.com - 2015-03-22 08:41 -0700
                Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-22 13:37 -0700
                Re: 8 queens problem in Oforth Bernd Paysan <bernd.paysan@gmx.de> - 2015-03-22 18:13 +0100
                Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-22 13:55 -0700
                Re: 8 queens problem in Oforth "Alex McDonald" <blog@rivadpm.com> - 2015-03-22 21:08 +0000
                Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-22 14:39 -0700
                Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-22 14:50 -0700
                Re: 8 queens problem in Oforth Bernd Paysan <bernd.paysan@gmx.de> - 2015-03-22 22:58 +0100
                Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-22 15:13 -0700
                Re: 8 queens problem in Oforth Bernd Paysan <bernd.paysan@gmx.de> - 2015-03-23 01:03 +0100
                Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-22 17:33 -0700
                Re: 8 queens problem in Oforth Bernd Paysan <bernd.paysan@gmx.de> - 2015-03-23 02:37 +0100
                Re: 8 queens problem in Oforth hughaguilar96@gmail.com - 2015-03-22 20:53 -0700
                Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-22 21:11 -0700
                Re: 8 queens problem in Oforth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-03-23 11:34 +0000
                Re: 8 queens problem in Oforth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-03-23 19:31 +0000
                Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-23 15:56 -0700
                Re: 8 queens problem in Oforth Bernd Paysan <bernd.paysan@gmx.de> - 2015-03-24 00:38 +0100
                Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-23 19:08 -0700
                Re: 8 queens problem in Oforth hughaguilar96@gmail.com - 2015-03-30 05:02 -0700
                Re: 8 queens problem in Oforth hughaguilar96@gmail.com - 2015-03-30 05:08 -0700
                Re: 8 queens problem in Oforth "Alex McDonald" <blog@rivadpm.com> - 2015-03-30 15:36 +0100
                Re: 8 queens problem in Oforth Bernd Paysan <bernd.paysan@gmx.de> - 2015-03-23 16:46 +0100
                Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-23 15:32 -0700
                Re: 8 queens problem in Oforth Bernd Paysan <bernd.paysan@gmx.de> - 2015-03-23 23:48 +0100
                Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-23 16:14 -0700
                Re: 8 queens problem in Oforth hughaguilar96@gmail.com - 2015-03-22 17:54 -0700
                Re: 8 queens problem in Oforth "Alex McDonald" <blog@rivadpm.com> - 2015-03-22 23:09 +0000
                Re: 8 queens problem in Oforth Bernd Paysan <bernd.paysan@gmx.de> - 2015-03-22 22:11 +0100
                Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-22 14:48 -0700
                Re: 8 queens problem in Oforth hughaguilar96@gmail.com - 2015-03-22 15:11 -0700
                Re: 8 queens problem in Oforth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-03-23 11:29 +0000
                Re: 8 queens problem in Oforth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-03-23 12:20 +0000
                Re: 8 queens problem in Oforth hughaguilar96@gmail.com - 2015-03-22 14:21 -0700
                Re: 8 queens problem in Oforth Coos Haak <chforth@hccnet.nl> - 2015-03-22 22:30 +0100
            Re: 8 queens problem in Oforth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-03-23 14:45 +0000
              Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-23 14:53 -0700
                Re: 8 queens problem in Oforth "Elizabeth D. Rather" <erather@forth.com> - 2015-03-24 09:16 -1000
                Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-24 12:40 -0700
                Re: 8 queens problem in Oforth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-03-30 12:24 +0000
          Re: 8 queens problem in Oforth Coos Haak <chforth@hccnet.nl> - 2015-03-21 22:27 +0100
  Re: 8 queens problem in Oforth "WJ" <w_a_x_man@yahoo.com> - 2015-03-19 20:31 +0000
  Re: 8 queens problem in Oforth "WJ" <w_a_x_man@yahoo.com> - 2015-03-19 20:35 +0000
  Re: 8 queens problem in Oforth "WJ" <w_a_x_man@yahoo.com> - 2015-03-21 17:31 +0000
    Re: 8 queens problem in Oforth "WJ" <w_a_x_man@yahoo.com> - 2015-03-21 20:50 +0000
    Re: 8 queens problem in Oforth "WJ" <w_a_x_man@yahoo.com> - 2015-03-21 21:52 +0000

csiph-web