Re: Seed7 programming language and big numbers



On 18 Apr., 06:47, Mensanator <mensana...@xxxxxxx> wrote:
On Apr 17, 1:44�pm, Mensanator <mensana...@xxxxxxx> wrote:

Sure, I'll put a copy on my website, same place as the Sedgewick
algorithm. I'll have to do that later when I have access to my
website. I'll post a note here when it's there. To be fair,
I didn't give it a 9-hour test like I did the Python version, but
it was taking much more time than I had patience for.

Ok, the Seed7 implementaion of Brent's algorithm
(I didn't do Floyd's as the Python test seemed to
show that Brent's was better for this application)
is now on my website:

<http://members.aol.com/mensanator/cycle/ecd.sd7>

Thank you.
Until now I have not found the time to benchmark it,

The first part of the file is a huge comment showing
the original Python code plus some test results. The
actual Seed7 code follows.

I would like to link to this example program from my
homepage. Is this ok or do you consider this file only
as temporary?

When the example program will stay there, I have some
wishes:
Could you improve the code such that I can link to it with
"Number theoretic program using Brent's algorithm".
Is the Python code at the beginning really necessary?
If someone follows the link and expects a Seed7 program
a comment containing Python code would be misleading.

Here's one of my test results using compiled Seed7:
(the 3 parameters are Start, End, C).

mensanator@DEEPESTTHOUGHT ~/gmp-4.1.2/seed7
$ ./ecd 1 2714 2097149

1
331
361
373
481
533
673
703
929
23963
70343
84103
2097149

time 5:00

Altough this used virtually no memory, look at the
time compared to my memory intensive C version:

mensanator@DEEPESTTHOUGHT ~/gmp-4.1.2
$ ./attractors023 1 2714 2097149 0
Attractors (initiators) loop_gcd
1 (1) 1
331 (41) 1
361 (13) 1
373 (59) 1
481 (29) 1
533 (11) 1
673 (3) 1
703 (5) 1
929 (25) 1
23963 (2319) 773
70343 (773) 773
84103 (2713) 2713
2097149 (2097149) 2097149

time 0:03.87

It really seems to be that this algorithm is faster.

So we're losing the memory/cpu tradeoff.

When I kick C up to a value that's intrabable memory-wise,

$ ./attractors023.exe 1 5000 536870909 1
Sequence Vector:
[29]

Error:Out of memory

It becomes way too slow using Brent's algorithm. Exactly how
slow I don't know, I never let it finish. The Python version
was still running after 9 hours.

I'm hoping that with Sedgewick's algorithm and a couple
hundred megs of fixed RAM, I can get a tractable run-time
in C.

Then we can see how it fares in Seed7 (if we can figure out
how to do that goofy C algorithm in Seed7).

I still did not manage to convert it to Seed7 (too busy
with GMP checks, gcd, modInvers, ...). OTOH I think that
my version of this algorithm is not up to date.

That number, 536870909, is a power of two minus 3 that's
prime, which seem particularly well suited to producing
extremely long loop cycles (it has at least one cycle of
19 million odd numbers). Speciffically, 2**29-3. The next
such prime is 2**94-3, so this may be the limit.

Greetings Thomas Mertes

Seed7 Homepage: http://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, portable, runs under linux/unix/windows.
.


Quantcast