On Apr 27, 8:58=A0am, thomas.mer...@[EMAIL PROTECTED]
wrote:
> On 25 Apr., 19:30, Mensanator <mensana...@[EMAIL PROTECTED]
> wrote:
>
>
>
>
>
> > On Apr 25, 7:01 am, thomas.mer...@[EMAIL PROTECTED]
wrote:
> > > On 25 Apr., 09:46, Mensanator <mensana...@[EMAIL PROTECTED]
> wrote:
> > > > On Apr 25, 1:30 am, thomas.mer...@[EMAIL PROTECTED]
wrote:
> > > > > Can you give me an update.
>
> > > > Trying to convert Sedgewick algorithm from C
> > > > to Seed7.
>
> > > > Quick question. I define an empty array using
>
> > > > =A0 var array cycle: cycle_stats is 0 times cycle.value
>
> > > > and then expand it one index at a time as needed by
>
> > > > =A0 cycle_stats &:=3D [](attractor_stats)
>
> > > This is possible, but it costs time to extend the array.
>
> > I expected that. I only do it s****adically and because I
> > have no way of predicting how big the array has to be.
> > It could be half a dozen or several hundred depending
> > on the idiosyncrasies of the Collatz function.
>
> > > You can request a bigger array at any time with:
>
> > > =A0 cycle_stats :=3D number times cycle.value;
>
> > Ah, that's what I was looking for, didn't know you could
> > do that dynamically.
>
> > > where 'number' is an integer variable. But note that
> > > such a statement replaces the whole array (The old
> > > content of the array is lost). There is also the possibility
> > > to increase an array:
>
> > > =A0 cycle_stats &:=3D 1000 times cycle.value;
>
> > > This way 1000 additional elements are added at the end of
> > > the array.
>
> > > > For the Sedgewick algorithm, the array gets created
> > > > as a fixed size M, but M is passed as a command line
> > > > parameter, so I can't do
>
> > > > =A0 var array cycle: cycle_stats is M times cycle.value
>
> > > > because M is unknown at compile time? Is that right?
>
> > > To use M in the declaration it must be known at compile
> > > time. But you can declare it with:
>
> > > =A0 var array cycle: cycle_stats is 0 times cycle.value;
>
> > > and use the statement
>
> > > =A0 cycle_stats :=3D M times cycle.value;
>
> > Thanks, that's exactly what I need. Apparently, the Sedgewick
> > algorithm needs to be tuned for optimum performance. Otherwise
> > you'll get a fault if the table is too small or performance
> > degradtion if too large.
>
> Why is there a problem when the table is too large?
> Does the program start thra****ng?
Well, there's not problem, it's a performance issue.
The table must be a certain size for the algorithm to work.
I don't know whether this is yet another fault in the
implementation of the program I downloaded or is caused
by my "fixes" or is inherent in Sedgewick.
For the test where the cycle is 19 million, a table sized
8 million produced a fault whereas 10 million didn't, so it
appears that I need a table somewhat larger than 50% of the
cycle, although exactly how large I haven't figured out.
For C=3D85085, the largest cycle is 264 and a table size of
1000 works fine. A table size of 100 faults and one of 200
works.
So why not just use a big table always? Because I have to
re-initialize the table every time I cahnge seeds, otherwise
the algorithm may think one of the table entries from a previous
run is a duplicate. It takes time to re-initialize a table,
so ideally, you don't want it larger than necessary. Often,
you have to test seed values in excess of C in order to find
all the cycles. That makes for a lot of re-initializing for
C=3D85085.
Trying this out as I'm typing this, although a table size of
200 works when the seed range was 1000, it failed when I raised
the seed range to 100000. But using a table of 2000 then worked.
Perhaps the algorithm is still a bit twitchy.
I'm not going to look at the C version anymore, we'll see what
happens when I finish the Seed7 conversion.
>
>
>
>
>
> > So the table size pretty much has to
> > be a command line parameter.
>
> > > to bring it to bigger size. This way M can be unknown
> > > at compile time.
>
> > > > Is there a way to create the entire array (M times)
> > > > in the program body instead of the variable declaration?
> > > > Without doing [](attractor_stats) M times?
>
> > > See above: cycle_stats :=3D M times cycle.value;
>
> > > > Also, working on my web page to summarize all this,
> > > > list the Seed7 programs, do some timing comparisons,
> > > > etc.
>
> > > > I notice the latest Seed7 seems much improved over
> > > > the previous one.
>
> > > I improved the built-in bigInteger sup****t (the one
> > > without GMP) to use bigdigits of 32 bit size. Before
> > > the size of a bigdigit was 16 bits.
>
> > > > I _thought_ the Brent algorithm
> > > > was rather slow in Seed7, but I didn't log it very
> > > > carefully and now it doesn't seem so bad. It may turn
> > > > out that Brent & Sedgewick are closer than I thought.
>
> > > > Trouble is, I don't have two of the same kind of fruit.
>
> > > > I've got attractors.c (naive cycle detection)
> > > > =A0 =A0 =A0 =A0 =A0efd.py =A0 =A0 =A0 (Brent)
> > > > =A0 =A0 =A0 =A0 =A0ecd001.sd7 =A0 (Brent) old Seed7
> > > > =A0 =A0 =A0 =A0 =A0ecd001.sd7 =A0 (Brent) current Seed7 with GMP
> > > > =A0 =A0 =A0 =A0 =A0ecd001.sd7 =A0 (Brent) current Seed7 without
GMP
> > > > =A0 =A0 =A0 =A0 =A0ccd020.c =A0 =A0 (Sedgewick)
>
> > > > And I'm trying to do testing and decide what to do
> > > > next. Nothing can touch the C programs, but Brent
> > > > in C isn't as much faster than I thought originally,
> > > > 39 sec for Seed7 vs 4.7 sec for C. How much of that
> > > > is due to the algorithm vs the language? Should I
> > > > make a Brent version in C along with a Sedgewick
> > > > version of Seed7?
>
> > > IMHO: For a comparison of language implementation speeds
> > > the same algorithm needs to be used.
>
> > Right. I need to focus on what I'm trying to accomplish and
> > that's NOT a language benchmark.
>
> No problem. If you think something in Seed7 is too slow tell
> me about it: I can profile compiled Seed7 programs.
Ok, I'll let you know as soon as I have the Seed7 version working.
You can check that while I finish up the web page.
>
> > What I want is a do***entary
> > on how I solved the problem, part of which will feature Seed7
> > (and give me an excuse to list all the sample sources in Seed7).
>
> Great.
>
> > I think when all the tradeoffs are considered, everything will
> > come out looking good.
>
> Greetings Thomas Mertes
>
> Seed7 Homepage: =A0http://seed7.sourceforge.net
> Seed7 - The extensible programming language: User defined statements
> and operators, abstract data types, templates without special
> syntax, OO with interfaces and multiple dispatch, statically typed,
> interpreted or compiled, ****table, runs under linux/unix/windows.- Hide
qu=
oted text -
>
> - Show quoted text -- Hide quoted text -
>
> - Show quoted text -
|
