On Apr 20, 3:51*pm, thomas.mer...@gmx.at wrote:

> - The file read_me.txt was improved to contain a chapter about
> * warnings and a chapter which explains how to use the GMP library.

I'm having problems with this (regular bigInt compiled fine).

I'm using cygwin and modified the makefile thusly:

# LIBS = c:/cygwin/usr/X11R6/lib/libX11.dll.a -lncurses -lm
LIBS = c:/cygwin/usr/X11R6/lib/libX11.dll.a -lncurses -lm C:/cygwin/
Seed7/seed7/lib/libgmp.a
SEED7_LIB = seed7_05.a
COMP_DATA_LIB = s7_data.a
COMPILER_LIB = s7_comp.a
CC = gcc

# BIGINT = big_rtl
BIGINT = big_gmp

I had to use a full path for my gmp library which is libgmp.a like I
had to do for
libX11.dll.a. Before that change, I had "file not found" errors.

Also, put gmp.h into Seed7/src folder, that made most of the
reference problems stop.

But I'm still getting

gcc hi.o s7_comp.a s7_data.a seed7_05.a c:/cygwin/usr/X11R6/lib/
libX11.dll.a -l
ncurses -lm C:/cygwin/Seed7/seed7/lib/libgmp.a -o hi
seed7_05.a(fil_rtl.o):fil_rtl.c.text+0x76): undefined reference to
`_bigUIConv'
seed7_05.a(fil_rtl.o):fil_rtl.c.text+0x11d): undefined reference to
`_bigUIConv'
Info: resolving _cur_term by linking to __imp__cur_term (auto-import)
collect2: ld returned 1 exit status
make: *** [hi] Error 1

Am I missing something? Or have a file in the wrong place?

On 22 Apr., 06:26, Mensanator wrote:
> On Apr 20, 3:51 pm, thomas.mer...@gmx.at wrote:
>
> > - The file read_me.txt was improved to contain a chapter about
> > warnings and a chapter which explains how to use the GMP library.
>
> I'm having problems with this (regular bigInt compiled fine).
>
> I'm using cygwin and modified the makefile thusly:
>
> # LIBS = c:/cygwin/usr/X11R6/lib/libX11.dll.a -lncurses -lm
> LIBS = c:/cygwin/usr/X11R6/lib/libX11.dll.a -lncurses -lm C:/cygwin/
> Seed7/seed7/lib/libgmp.a
> SEED7_LIB = seed7_05.a
> COMP_DATA_LIB = s7_data.a
> COMPILER_LIB = s7_comp.a
> CC = gcc
>
> # BIGINT = big_rtl
> BIGINT = big_gmp
>
> I had to use a full path for my gmp library which is libgmp.a like I
> had to do for
> libX11.dll.a. Before that change, I had "file not found" errors.
>
> Also, put gmp.h into Seed7/src folder, that made most of the
> reference problems stop.
>
> But I'm still getting
>
> gcc hi.o s7_comp.a s7_data.a seed7_05.a c:/cygwin/usr/X11R6/lib/
> libX11.dll.a -l
> ncurses -lm C:/cygwin/Seed7/seed7/lib/libgmp.a -o hi
> seed7_05.a(fil_rtl.o):fil_rtl.c.text+0x76): undefined reference to
> `_bigUIConv'
> seed7_05.a(fil_rtl.o):fil_rtl.c.text+0x11d): undefined reference to
> `_bigUIConv'
> Info: resolving _cur_term by linking to __imp__cur_term (auto-import)
> collect2: ld returned 1 exit status
> make: *** [hi] Error 1
>
> Am I missing something? Or have a file in the wrong place?

All files are at the right place. The function bigUIConv is
really missing from the file big_gmp.c . Sorry, but I had not
the possibility to check cygwin (linux and MinGW do not need
it). The good message is: bigUIConv is very simple:

----------------------------------------
#ifdef ANSI_C

gmpBiginttype bigUIConv (inttype number)
#else

gmpBiginttype bigUIConv (number)
inttype number;
#endif

{
gmpBiginttype result;

/* bigUIConv */
result = malloc(sizeof(__mpz_struct));
mpz_init_set_ui(result, number);
return(result);
} /* bigUIConv */
----------------------------------------

If you add it at the end of the file big_gmp.c you should
succeed.

I hope that helps. Sorry for the trouble.
If there are other problems: Please tell me.

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.

On Apr 22, 1:46*am, thomas.mer...@gmx.at wrote:
> On 22 Apr., 06:26, Mensanator wrote:
>
>
>
>
>
> > On Apr 20, 3:51 pm, thomas.mer...@gmx.at wrote:
>
> > > - The file read_me.txt was improved to contain a chapter about
> > > * warnings and a chapter which explains how to use the GMP library.
>
> > I'm having problems with this (regular bigInt compiled fine).
>
> > I'm using cygwin and modified the makefile thusly:
>
> > # LIBS = c:/cygwin/usr/X11R6/lib/libX11.dll.a -lncurses -lm
> > LIBS = c:/cygwin/usr/X11R6/lib/libX11.dll.a -lncurses -lm C:/cygwin/
> > Seed7/seed7/lib/libgmp.a
> > SEED7_LIB = seed7_05.a
> > COMP_DATA_LIB = s7_data.a
> > COMPILER_LIB = s7_comp.a
> > CC = gcc
>
> > # BIGINT = big_rtl
> > BIGINT = big_gmp
>
> > I had to use a full path for my gmp library which is libgmp.a like I
> > had to do for
> > libX11.dll.a. Before that change, I had "file not found" errors.
>
> > Also, put gmp.h into Seed7/src folder, that made most of the
> > reference problems stop.
>
> > But I'm still getting
>
> > gcc *hi.o s7_comp.a s7_data.a seed7_05.a c:/cygwin/usr/X11R6/lib/
> > libX11.dll.a -l
> > ncurses -lm C:/cygwin/Seed7/seed7/lib/libgmp.a -o hi
> > seed7_05.a(fil_rtl.o):fil_rtl.c.text+0x76): undefined reference to
> > `_bigUIConv'
> > seed7_05.a(fil_rtl.o):fil_rtl.c.text+0x11d): undefined reference to
> > `_bigUIConv'
> > Info: resolving _cur_term by linking to __imp__cur_term (auto-import)
> > collect2: ld returned 1 exit status
> > make: *** [hi] Error 1
>
> > Am I missing something? Or have a file in the wrong place?
>
> All files are at the right place. The function bigUIConv is
> really missing from the file big_gmp.c . Sorry, but I had not
> the possibility to check cygwin (linux and MinGW do not need
> it). The good message is: bigUIConv is very simple:
>
> ----------------------------------------
> #ifdef ANSI_C
>
> gmpBiginttype bigUIConv (inttype number)
> #else
>
> gmpBiginttype bigUIConv (number)
> inttype number;
> #endif
>
> * {
> * * gmpBiginttype result;
>
> * /* bigUIConv */
> * * result = malloc(sizeof(__mpz_struct));
> * * mpz_init_set_ui(result, number);
> * * return(result);
> * } /* bigUIConv */
> ----------------------------------------
>
> If you add it at the end of the file big_gmp.c you should
> succeed.
>
> I hope that helps. Sorry for the trouble.

Thanks! That fixed it.

Hate to be a pest, but I've got three different machines with
three different cygwin configurations. I try my best to resolve
things, but compilers aren't my forte. I even considered trying
to find the missing reference, but I can see that I never would
have resolved it.

> If there are other problems: Please tell me.

I haven't had time to run it yet, but I plan to use the gmp
version when I do a Seed7 implementation of Sedgewick's
algorithm and we don't want my C version to have an unfair
advantage.

>
> 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.- Hide quoted text -
>
> - Show quoted text -

On 22 Apr., 19:09, Mensanator wrote:
> On Apr 22, 1:46 am, thomas.mer...@gmx.at wrote:
> > On 22 Apr., 06:26, Mensanator wrote:
> > > On Apr 20, 3:51 pm, thomas.mer...@gmx.at wrote:
> > > > - The file read_me.txt was improved to contain a chapter about
> > > > warnings and a chapter which explains how to use the GMP library.
>
> > > I'm having problems with this (regular bigInt compiled fine).
>
> > > I'm using cygwin and modified the makefile thusly:
>
> > > # LIBS = c:/cygwin/usr/X11R6/lib/libX11.dll.a -lncurses -lm
> > > LIBS = c:/cygwin/usr/X11R6/lib/libX11.dll.a -lncurses -lm C:/cygwin/
> > > Seed7/seed7/lib/libgmp.a
> > > SEED7_LIB = seed7_05.a
> > > COMP_DATA_LIB = s7_data.a
> > > COMPILER_LIB = s7_comp.a
> > > CC = gcc
>
> > > # BIGINT = big_rtl
> > > BIGINT = big_gmp
>
> > > I had to use a full path for my gmp library which is libgmp.a like I
> > > had to do for
> > > libX11.dll.a. Before that change, I had "file not found" errors.
>
> > > Also, put gmp.h into Seed7/src folder, that made most of the
> > > reference problems stop.
>
> > > But I'm still getting
>
> > > gcc hi.o s7_comp.a s7_data.a seed7_05.a c:/cygwin/usr/X11R6/lib/
> > > libX11.dll.a -l
> > > ncurses -lm C:/cygwin/Seed7/seed7/lib/libgmp.a -o hi
> > > seed7_05.a(fil_rtl.o):fil_rtl.c.text+0x76): undefined reference to
> > > `_bigUIConv'
> > > seed7_05.a(fil_rtl.o):fil_rtl.c.text+0x11d): undefined reference to
> > > `_bigUIConv'
> > > Info: resolving _cur_term by linking to __imp__cur_term (auto-import)
> > > collect2: ld returned 1 exit status
> > > make: *** [hi] Error 1
>
> > > Am I missing something? Or have a file in the wrong place?
>
> > All files are at the right place. The function bigUIConv is
> > really missing from the file big_gmp.c . Sorry, but I had not
> > the possibility to check cygwin (linux and MinGW do not need
> > it). The good message is: bigUIConv is very simple:
>
> > ----------------------------------------
> > #ifdef ANSI_C
>
> > gmpBiginttype bigUIConv (inttype number)
> > #else
>
> > gmpBiginttype bigUIConv (number)
> > inttype number;
> > #endif
>
> > {
> > gmpBiginttype result;
>
> > /* bigUIConv */
> > result = malloc(sizeof(__mpz_struct));
> > mpz_init_set_ui(result, number);
> > return(result);
> > } /* bigUIConv */
> > ----------------------------------------
>
> > If you add it at the end of the file big_gmp.c you should
> > succeed.
>
> > I hope that helps. Sorry for the trouble.
>
> Thanks! That fixed it.
>
> Hate to be a pest, but I've got three different machines with
> three different cygwin configurations. I try my best to resolve
> things, but compilers aren't my forte. I even considered trying
> to find the missing reference, but I can see that I never would
> have resolved it.
>
> > If there are other problems: Please tell me.
>
> I haven't had time to run it yet, but I plan to use the gmp
> version when I do a Seed7 implementation of Sedgewick's
> algorithm and we don't want my C version to have an unfair
> advantage.

Can you give me an update.
What should I add to the next release (except for a faster
modInverse function)?

BTW.: What results does mpz_invert(rop, op1, op2) have when
op2 is negative? Is it defined at all? Is there some relation like:
mpz_invert(rop, op1, -op2) = mpz_invert(rop, op1, op2)

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.

On Apr 25, 1:30*am, thomas.mer...@gmx.at wrote:
> On 22 Apr., 19:09, Mensanator wrote:
>
>
>
>
>
> > On Apr 22, 1:46 am, thomas.mer...@gmx.at wrote:
> > > On 22 Apr., 06:26, Mensanator wrote:
> > > > On Apr 20, 3:51 pm, thomas.mer...@gmx.at wrote:
> > > > > - The file read_me.txt was improved to contain a chapter about
> > > > > * warnings and a chapter which explains how to use the GMP library.
>
> > > > I'm having problems with this (regular bigInt compiled fine).
>
> > > > I'm using cygwin and modified the makefile thusly:
>
> > > > # LIBS = c:/cygwin/usr/X11R6/lib/libX11.dll.a -lncurses -lm
> > > > LIBS = c:/cygwin/usr/X11R6/lib/libX11.dll.a -lncurses -lm C:/cygwin/
> > > > Seed7/seed7/lib/libgmp.a
> > > > SEED7_LIB = seed7_05.a
> > > > COMP_DATA_LIB = s7_data.a
> > > > COMPILER_LIB = s7_comp.a
> > > > CC = gcc
>
> > > > # BIGINT = big_rtl
> > > > BIGINT = big_gmp
>
> > > > I had to use a full path for my gmp library which is libgmp.a like I
> > > > had to do for
> > > > libX11.dll.a. Before that change, I had "file not found" errors.
>
> > > > Also, put gmp.h into Seed7/src folder, that made most of the
> > > > reference problems stop.
>
> > > > But I'm still getting
>
> > > > gcc *hi.o s7_comp.a s7_data.a seed7_05.a c:/cygwin/usr/X11R6/lib/
> > > > libX11.dll.a -l
> > > > ncurses -lm C:/cygwin/Seed7/seed7/lib/libgmp.a -o hi
> > > > seed7_05.a(fil_rtl.o):fil_rtl.c.text+0x76): undefined reference to
> > > > `_bigUIConv'
> > > > seed7_05.a(fil_rtl.o):fil_rtl.c.text+0x11d): undefined reference to
> > > > `_bigUIConv'
> > > > Info: resolving _cur_term by linking to __imp__cur_term (auto-import)
> > > > collect2: ld returned 1 exit status
> > > > make: *** [hi] Error 1
>
> > > > Am I missing something? Or have a file in the wrong place?
>
> > > All files are at the right place. The function bigUIConv is
> > > really missing from the file big_gmp.c . Sorry, but I had not
> > > the possibility to check cygwin (linux and MinGW do not need
> > > it). The good message is: bigUIConv is very simple:
>
> > > ----------------------------------------
> > > #ifdef ANSI_C
>
> > > gmpBiginttype bigUIConv (inttype number)
> > > #else
>
> > > gmpBiginttype bigUIConv (number)
> > > inttype number;
> > > #endif
>
> > > * {
> > > * * gmpBiginttype result;
>
> > > * /* bigUIConv */
> > > * * result = malloc(sizeof(__mpz_struct));
> > > * * mpz_init_set_ui(result, number);
> > > * * return(result);
> > > * } /* bigUIConv */
> > > ----------------------------------------
>
> > > If you add it at the end of the file big_gmp.c you should
> > > succeed.
>
> > > I hope that helps. Sorry for the trouble.
>
> > Thanks! That fixed it.
>
> > Hate to be a pest, but I've got three different machines with
> > three different cygwin configurations. I try my best to resolve
> > things, but compilers aren't my forte. I even considered trying
> > to find the missing reference, but I can see that I never would
> > have resolved it.
>
> > > If there are other problems: Please tell me.
>
> > I haven't had time to run it yet, but I plan to use the gmp
> > version when I do a Seed7 implementation of Sedgewick's
> > algorithm and we don't want my C version to have an unfair
> > advantage.
>
> Can you give me an update.

Trying to convert Sedgewick algorithm from C
to Seed7.

Quick question. I define an empty array using

var array cycle: cycle_stats is 0 times cycle.value

and then expand it one index at a time as needed by

cycle_stats &:= [](attractor_stats)

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

var array cycle: cycle_stats is M times cycle.value

because M is unknown at compile time? Is that right?

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?

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 _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)
efd.py (Brent)
ecd001.sd7 (Brent) old Seed7
ecd001.sd7 (Brent) current Seed7 with GMP
ecd001.sd7 (Brent) current Seed7 without GMP
ccd020.c (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?

Oh, and this cycle detection is one place where GMP
makes it worse (68 sec), not better. Yet GMP outperforms
Seed7 bigIntegers in the Collatz test of large Mersenne
numbers. Excessive overhead in setting up the mpz's
using up the time savings, so it depends on ratio
of variables to operations?

Anyway, I'm still trying to collate the big picture.

> What should I add to the next release (except for a faster
> modInverse function)?

I haven't given it much thought.

>
> BTW.: What results does mpz_invert(rop, op1, op2) have when
> op2 is negative?

Same as positive, apparently.

>>> import gmpy
>>> gmpy.invert(8,9)
mpz(8)
>>> gmpy.invert(8,-9)
mpz(8)
>>> for j in xrange(1,10):
for i in xrange(2,10):
print gmpy.invert(j,i),
print
1 1 1 1 1 1 1 1
0 2 0 3 0 4 0 5
1 0 3 2 0 5 3 0
0 1 0 4 0 2 0 7
1 2 1 0 5 3 5 2
0 0 0 1 0 6 0 0
1 1 3 3 1 0 7 4
0 2 0 2 0 1 0 8
1 0 1 4 0 4 1 0


>>> for j in xrange(1,10):
for i in xrange(-2,-10,-1):
print gmpy.invert(j,i),
print
1 1 1 1 1 1 1 1
0 2 0 3 0 4 0 5
1 0 3 2 0 5 3 0
0 1 0 4 0 2 0 7
1 2 1 0 5 3 5 2
0 0 0 1 0 6 0 0
1 1 3 3 1 0 7 4
0 2 0 2 0 1 0 8
1 0 1 4 0 4 1 0

The gmpy help says just that it not be zero:

Help on built-in function invert in module gmpy:

invert(...)
invert(x,m): returns the inverse of x modulo m, i.e.,
that y such that x*y==1 modulo m, or 0 if no such
y exists.
m must be an ordinary Python int, !=0;
x must be an mpz, or else gets converted to one.

The GNU GMP manual says:

int mpz_invert (mpz t rop, mpz t op1, mpz t op2) [Function]
Compute the inverse of op1 modulo op2 and
put the result in rop. If the inverse exists,
the return value is non-zero and rop will satisfy
0 <= rop < op2. If an inverse doesn’t exist the
return value is zero and rop is undefined


> Is it defined at all?

Well, it doesn't say you CAN'T use negative operands.
Does "rop will satisfy 0 <= rop < op2" mean that rop
COULD be negative? Seems rather ambiguous to me.

Of course, the above test is in Python, it MIGHT be
different in C. For example, the linear congruence
solver divm() is not a GMP function. It is a value-added
feature of the gmpy wrapper of GMP. In divm(), "not
invertable" throws an exception although a direct call
to invert() does not, it simply returns 0.

> Is there some relation like:
> mpz_invert(rop, op1, -op2) = mpz_invert(rop, op1, op2)
>
> 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.

On Apr 25, 2:46*am, Mensanator wrote:
> On Apr 25, 1:30*am, thomas.mer...@gmx.at wrote:
>
>
>
>
>
> > On 22 Apr., 19:09, Mensanator wrote:
>
> > > On Apr 22, 1:46 am, thomas.mer...@gmx.at wrote:
> > > > On 22 Apr., 06:26, Mensanator wrote:
> > > > > On Apr 20, 3:51 pm, thomas.mer...@gmx.at wrote:
> > > > > > - The file read_me.txt was improved to contain a chapter about
> > > > > > * warnings and a chapter which explains how to use the GMP library.
>
> > > > > I'm having problems with this (regular bigInt compiled fine).
>
> > > > > I'm using cygwin and modified the makefile thusly:
>
> > > > > # LIBS = c:/cygwin/usr/X11R6/lib/libX11.dll.a -lncurses -lm
> > > > > LIBS = c:/cygwin/usr/X11R6/lib/libX11.dll.a -lncurses -lm C:/cygwin/
> > > > > Seed7/seed7/lib/libgmp.a
> > > > > SEED7_LIB = seed7_05.a
> > > > > COMP_DATA_LIB = s7_data.a
> > > > > COMPILER_LIB = s7_comp.a
> > > > > CC = gcc
>
> > > > > # BIGINT = big_rtl
> > > > > BIGINT = big_gmp
>
> > > > > I had to use a full path for my gmp library which is libgmp.a likeI
> > > > > had to do for
> > > > > libX11.dll.a. Before that change, I had "file not found" errors.
>
> > > > > Also, put gmp.h into Seed7/src folder, that made most of the
> > > > > reference problems stop.
>
> > > > > But I'm still getting
>
> > > > > gcc *hi.o s7_comp.a s7_data.a seed7_05.a c:/cygwin/usr/X11R6/lib/
> > > > > libX11.dll.a -l
> > > > > ncurses -lm C:/cygwin/Seed7/seed7/lib/libgmp.a -o hi
> > > > > seed7_05.a(fil_rtl.o):fil_rtl.c.text+0x76): undefined reference to
> > > > > `_bigUIConv'
> > > > > seed7_05.a(fil_rtl.o):fil_rtl.c.text+0x11d): undefined referenceto
> > > > > `_bigUIConv'
> > > > > Info: resolving _cur_term by linking to __imp__cur_term (auto-import)
> > > > > collect2: ld returned 1 exit status
> > > > > make: *** [hi] Error 1
>
> > > > > Am I missing something? Or have a file in the wrong place?
>
> > > > All files are at the right place. The function bigUIConv is
> > > > really missing from the file big_gmp.c . Sorry, but I had not
> > > > the possibility to check cygwin (linux and MinGW do not need
> > > > it). The good message is: bigUIConv is very simple:
>
> > > > ----------------------------------------
> > > > #ifdef ANSI_C
>
> > > > gmpBiginttype bigUIConv (inttype number)
> > > > #else
>
> > > > gmpBiginttype bigUIConv (number)
> > > > inttype number;
> > > > #endif
>
> > > > * {
> > > > * * gmpBiginttype result;
>
> > > > * /* bigUIConv */
> > > > * * result = malloc(sizeof(__mpz_struct));
> > > > * * mpz_init_set_ui(result, number);
> > > > * * return(result);
> > > > * } /* bigUIConv */
> > > > ----------------------------------------
>
> > > > If you add it at the end of the file big_gmp.c you should
> > > > succeed.
>
> > > > I hope that helps. Sorry for the trouble.
>
> > > Thanks! That fixed it.
>
> > > Hate to be a pest, but I've got three different machines with
> > > three different cygwin configurations. I try my best to resolve
> > > things, but compilers aren't my forte. I even considered trying
> > > to find the missing reference, but I can see that I never would
> > > have resolved it.
>
> > > > If there are other problems: Please tell me.
>
> > > I haven't had time to run it yet, but I plan to use the gmp
> > > version when I do a Seed7 implementation of Sedgewick's
> > > algorithm and we don't want my C version to have an unfair
> > > advantage.
>
> > Can you give me an update.
>
> Trying to convert Sedgewick algorithm from C
> to Seed7.
>
> Quick question. I define an empty array using
>
> * var array cycle: cycle_stats is 0 times cycle.value
>
> and then expand it one index at a time as needed by
>
> * cycle_stats &:= [](attractor_stats)
>
> 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
>
> * var array cycle: cycle_stats is M times cycle.value
>
> because M is unknown at compile time? Is that right?
>
> 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?
>
> 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 _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)
> * * * * *efd.py * * * (Brent)
> * * * * *ecd001.sd7 * (Brent) old Seed7
> * * * * *ecd001.sd7 * (Brent) current Seed7 with GMP
> * * * * *ecd001.sd7 * (Brent) current Seed7 without GMP
> * * * * *ccd020.c * * (Sedgewick)
>
> And I'm trying to do testing and decide what to do
> next. Nothing can touch the C programs, but Brent

Oops! That was supposed to be Sedgewick, I don't
have Brent's algorithm in C.

> 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?
>
> Oh, and this cycle detection is one place where GMP
> makes it worse (68 sec), not better. Yet GMP outperforms
> Seed7 bigIntegers in the Collatz test of large Mersenne
> numbers. Excessive overhead in setting up the mpz's
> using up the time savings, so it depends on ratio
> of variables to operations?
>
> Anyway, I'm still trying to collate the big picture.
>
> > What should I add to the next release (except for a faster
> > modInverse function)?
>
> I haven't given it much thought.
>
>
>
> > BTW.: What results does mpz_invert(rop, op1, op2) have when
> > op2 is negative?
>
> Same as positive, apparently.
>
> >>> import gmpy
> >>> gmpy.invert(8,9)
> mpz(8)
> >>> gmpy.invert(8,-9)
> mpz(8)
> >>> for j in xrange(1,10):
>
> * * * * for i in xrange(2,10):
> * * * * * * * * print gmpy.invert(j,i),
> * * * * print
> 1 1 1 1 1 1 1 1
> 0 2 0 3 0 4 0 5
> 1 0 3 2 0 5 3 0
> 0 1 0 4 0 2 0 7
> 1 2 1 0 5 3 5 2
> 0 0 0 1 0 6 0 0
> 1 1 3 3 1 0 7 4
> 0 2 0 2 0 1 0 8
> 1 0 1 4 0 4 1 0
>
> >>> for j in xrange(1,10):
>
> * * * * for i in xrange(-2,-10,-1):
> * * * * * * * * print gmpy.invert(j,i),
> * * * * print
> 1 1 1 1 1 1 1 1
> 0 2 0 3 0 4 0 5
> 1 0 3 2 0 5 3 0
> 0 1 0 4 0 2 0 7
> 1 2 1 0 5 3 5 2
> 0 0 0 1 0 6 0 0
> 1 1 3 3 1 0 7 4
> 0 2 0 2 0 1 0 8
> 1 0 1 4 0 4 1 0
>
> The gmpy help says just that it not be zero:
>
> Help on built-in function invert in module gmpy:
>
> invert(...)
> * * invert(x,m): returns the inverse of x modulo m, i.e.,
> * * that y such that x*y==1 modulo m, or 0 if no such
> * * y exists.
> * * m must be an ordinary Python int, !=0;
> * * x must be an mpz, or else gets converted to one.
>
> The GNU GMP manual says:
>
> int mpz_invert (mpz t rop, mpz t op1, mpz t op2) [Function]
> * Compute the inverse of op1 modulo op2 and
> * put the result in rop. If the inverse exists,
> * the return value is non-zero and rop will satisfy
> * 0 <= rop < op2. If an inverse doesn’t exist the
> * return value is zero and rop is undefined
>
> > Is it defined at all?
>
> Well, it doesn't say you CAN'T use negative operands.
> Does "rop will satisfy 0 <= rop < op2" mean that rop
> COULD be negative? Seems rather ambiguous to me.
>
> Of course, the above test is in Python, it MIGHT be
> different in C. For example, the linear congruence
> solver divm() is not a GMP function. It is a value-added
> feature of the gmpy wrapper of GMP. In divm(), "not
> invertable" throws an exception although a direct call
> to invert() does not, it simply returns 0.
>
>
>
> > Is there some relation like:
> > mpz_invert(rop, op1, -op2) = mpz_invert(rop, op1, op2)
>
> > 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.- Hide quoted text -
>
> - Show quoted text -- Hide quoted text -
>
> - Show quoted text -

On 25 Apr., 09:46, Mensanator wrote:
> On Apr 25, 1:30 am, thomas.mer...@gmx.at wrote:
> > On 22 Apr., 19:09, Mensanator wrote:
> > > On Apr 22, 1:46 am, thomas.mer...@gmx.at wrote:
> > > > On 22 Apr., 06:26, Mensanator wrote:
> > > > > On Apr 20, 3:51 pm, thomas.mer...@gmx.at wrote:
> > > > > > - The file read_me.txt was improved to contain a chapter about
> > > > > > warnings and a chapter which explains how to use the GMP library.
>
> > > > > I'm having problems with this (regular bigInt compiled fine).
>
> > > > > I'm using cygwin and modified the makefile thusly:
>
> > > > > # LIBS = c:/cygwin/usr/X11R6/lib/libX11.dll.a -lncurses -lm
> > > > > LIBS = c:/cygwin/usr/X11R6/lib/libX11.dll.a -lncurses -lm C:/cygwin/
> > > > > Seed7/seed7/lib/libgmp.a
> > > > > SEED7_LIB = seed7_05.a
> > > > > COMP_DATA_LIB = s7_data.a
> > > > > COMPILER_LIB = s7_comp.a
> > > > > CC = gcc
>
> > > > > # BIGINT = big_rtl
> > > > > BIGINT = big_gmp
>
> > > > > I had to use a full path for my gmp library which is libgmp.a likeI
> > > > > had to do for
> > > > > libX11.dll.a. Before that change, I had "file not found" errors.
>
> > > > > Also, put gmp.h into Seed7/src folder, that made most of the
> > > > > reference problems stop.
>
> > > > > But I'm still getting
>
> > > > > gcc hi.o s7_comp.a s7_data.a seed7_05.a c:/cygwin/usr/X11R6/lib/
> > > > > libX11.dll.a -l
> > > > > ncurses -lm C:/cygwin/Seed7/seed7/lib/libgmp.a -o hi
> > > > > seed7_05.a(fil_rtl.o):fil_rtl.c.text+0x76): undefined reference to
> > > > > `_bigUIConv'
> > > > > seed7_05.a(fil_rtl.o):fil_rtl.c.text+0x11d): undefined referenceto
> > > > > `_bigUIConv'
> > > > > Info: resolving _cur_term by linking to __imp__cur_term (auto-import)
> > > > > collect2: ld returned 1 exit status
> > > > > make: *** [hi] Error 1
>
> > > > > Am I missing something? Or have a file in the wrong place?
>
> > > > All files are at the right place. The function bigUIConv is
> > > > really missing from the file big_gmp.c . Sorry, but I had not
> > > > the possibility to check cygwin (linux and MinGW do not need
> > > > it). The good message is: bigUIConv is very simple:
>
> > > > ----------------------------------------
> > > > #ifdef ANSI_C
>
> > > > gmpBiginttype bigUIConv (inttype number)
> > > > #else
>
> > > > gmpBiginttype bigUIConv (number)
> > > > inttype number;
> > > > #endif
>
> > > > {
> > > > gmpBiginttype result;
>
> > > > /* bigUIConv */
> > > > result = malloc(sizeof(__mpz_struct));
> > > > mpz_init_set_ui(result, number);
> > > > return(result);
> > > > } /* bigUIConv */
> > > > ----------------------------------------
>
> > > > If you add it at the end of the file big_gmp.c you should
> > > > succeed.
>
> > > > I hope that helps. Sorry for the trouble.
>
> > > Thanks! That fixed it.
>
> > > Hate to be a pest, but I've got three different machines with
> > > three different cygwin configurations. I try my best to resolve
> > > things, but compilers aren't my forte. I even considered trying
> > > to find the missing reference, but I can see that I never would
> > > have resolved it.
>
> > > > If there are other problems: Please tell me.
>
> > > I haven't had time to run it yet, but I plan to use the gmp
> > > version when I do a Seed7 implementation of Sedgewick's
> > > algorithm and we don't want my C version to have an unfair
> > > advantage.
>
> > Can you give me an update.
>
> Trying to convert Sedgewick algorithm from C
> to Seed7.
>
> Quick question. I define an empty array using
>
> var array cycle: cycle_stats is 0 times cycle.value
>
> and then expand it one index at a time as needed by
>
> cycle_stats &:= [](attractor_stats)

This is possible, but it costs time to extend the array.
You can request a bigger array at any time with:

cycle_stats := number times cycle.value;

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:

cycle_stats &:= 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
>
> 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:

var array cycle: cycle_stats is 0 times cycle.value;

and use the statement

cycle_stats := M times cycle.value;

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 := 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 support (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)
> efd.py (Brent)
> ecd001.sd7 (Brent) old Seed7
> ecd001.sd7 (Brent) current Seed7 with GMP
> ecd001.sd7 (Brent) current Seed7 without GMP
> ccd020.c (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.

> Oh, and this cycle detection is one place where GMP
> makes it worse (68 sec), not better. Yet GMP outperforms
> Seed7 bigIntegers in the Collatz test of large Mersenne
> numbers. Excessive overhead in setting up the mpz's
> using up the time savings, so it depends on ratio
> of variables to operations?
>
> Anyway, I'm still trying to collate the big picture.
>
> > What should I add to the next release (except for a faster
> > modInverse function)?
>
> I haven't given it much thought.
>
>
> > BTW.: What results does mpz_invert(rop, op1, op2) have when
> > op2 is negative?
>
> Same as positive, apparently.
>
> >>> import gmpy
> >>> gmpy.invert(8,9)
> mpz(8)
> >>> gmpy.invert(8,-9)
> mpz(8)
> >>> for j in xrange(1,10):
>
> for i in xrange(2,10):
> print gmpy.invert(j,i),
> print
> 1 1 1 1 1 1 1 1
> 0 2 0 3 0 4 0 5
> 1 0 3 2 0 5 3 0
> 0 1 0 4 0 2 0 7
> 1 2 1 0 5 3 5 2
> 0 0 0 1 0 6 0 0
> 1 1 3 3 1 0 7 4
> 0 2 0 2 0 1 0 8
> 1 0 1 4 0 4 1 0
>
> >>> for j in xrange(1,10):
>
> for i in xrange(-2,-10,-1):
> print gmpy.invert(j,i),
> print
> 1 1 1 1 1 1 1 1
> 0 2 0 3 0 4 0 5
> 1 0 3 2 0 5 3 0
> 0 1 0 4 0 2 0 7
> 1 2 1 0 5 3 5 2
> 0 0 0 1 0 6 0 0
> 1 1 3 3 1 0 7 4
> 0 2 0 2 0 1 0 8
> 1 0 1 4 0 4 1 0
>
> The gmpy help says just that it not be zero:
>
> Help on built-in function invert in module gmpy:
>
> invert(...)
> invert(x,m): returns the inverse of x modulo m, i.e.,
> that y such that x*y==1 modulo m, or 0 if no such
> y exists.
> m must be an ordinary Python int, !=0;
> x must be an mpz, or else gets converted to one.
>
> The GNU GMP manual says:
>
> int mpz_invert (mpz t rop, mpz t op1, mpz t op2) [Function]
> Compute the inverse of op1 modulo op2 and
> put the result in rop. If the inverse exists,
> the return value is non-zero and rop will satisfy
> 0 <= rop < op2. If an inverse doesn’t exist the
> return value is zero and rop is undefined
>
> > Is it defined at all?
>
> Well, it doesn't say you CAN'T use negative operands.
> Does "rop will satisfy 0 <= rop < op2" mean that rop
> COULD be negative? Seems rather ambiguous to me.

That is also my impression.

> Of course, the above test is in Python, it MIGHT be
> different in C. For example, the linear congruence
> solver divm() is not a GMP function. It is a value-added
> feature of the gmpy wrapper of GMP. In divm(), "not
> invertable" throws an exception although a direct call
> to invert() does not, it simply returns 0.

Thank you for the information.

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.

On Apr 25, 7:01*am, thomas.mer...@gmx.at wrote:
> On 25 Apr., 09:46, Mensanator wrote:
>
>
>
>
>
> > On Apr 25, 1:30 am, thomas.mer...@gmx.at wrote:
> > > On 22 Apr., 19:09, Mensanator wrote:
> > > > On Apr 22, 1:46 am, thomas.mer...@gmx.at wrote:
> > > > > On 22 Apr., 06:26, Mensanator wrote:
> > > > > > On Apr 20, 3:51 pm, thomas.mer...@gmx.at wrote:
> > > > > > > - The file read_me.txt was improved to contain a chapter about
> > > > > > > * warnings and a chapter which explains how to use the GMP library.
>
> > > > > > I'm having problems with this (regular bigInt compiled fine).
>
> > > > > > I'm using cygwin and modified the makefile thusly:
>
> > > > > > # LIBS = c:/cygwin/usr/X11R6/lib/libX11.dll.a -lncurses -lm
> > > > > > LIBS = c:/cygwin/usr/X11R6/lib/libX11.dll.a -lncurses -lm C:/cygwin/
> > > > > > Seed7/seed7/lib/libgmp.a
> > > > > > SEED7_LIB = seed7_05.a
> > > > > > COMP_DATA_LIB = s7_data.a
> > > > > > COMPILER_LIB = s7_comp.a
> > > > > > CC = gcc
>
> > > > > > # BIGINT = big_rtl
> > > > > > BIGINT = big_gmp
>
> > > > > > I had to use a full path for my gmp library which is libgmp.a like I
> > > > > > had to do for
> > > > > > libX11.dll.a. Before that change, I had "file not found" errors.
>
> > > > > > Also, put gmp.h into Seed7/src folder, that made most of the
> > > > > > reference problems stop.
>
> > > > > > But I'm still getting
>
> > > > > > gcc *hi.o s7_comp.a s7_data.a seed7_05.a c:/cygwin/usr/X11R6/lib/
> > > > > > libX11.dll.a -l
> > > > > > ncurses -lm C:/cygwin/Seed7/seed7/lib/libgmp.a -o hi
> > > > > > seed7_05.a(fil_rtl.o):fil_rtl.c.text+0x76): undefined reference to
> > > > > > `_bigUIConv'
> > > > > > seed7_05.a(fil_rtl.o):fil_rtl.c.text+0x11d): undefined reference to
> > > > > > `_bigUIConv'
> > > > > > Info: resolving _cur_term by linking to __imp__cur_term (auto-import)
> > > > > > collect2: ld returned 1 exit status
> > > > > > make: *** [hi] Error 1
>
> > > > > > Am I missing something? Or have a file in the wrong place?
>
> > > > > All files are at the right place. The function bigUIConv is
> > > > > really missing from the file big_gmp.c . Sorry, but I had not
> > > > > the possibility to check cygwin (linux and MinGW do not need
> > > > > it). The good message is: bigUIConv is very simple:
>
> > > > > ----------------------------------------
> > > > > #ifdef ANSI_C
>
> > > > > gmpBiginttype bigUIConv (inttype number)
> > > > > #else
>
> > > > > gmpBiginttype bigUIConv (number)
> > > > > inttype number;
> > > > > #endif
>
> > > > > * {
> > > > > * * gmpBiginttype result;
>
> > > > > * /* bigUIConv */
> > > > > * * result = malloc(sizeof(__mpz_struct));
> > > > > * * mpz_init_set_ui(result, number);
> > > > > * * return(result);
> > > > > * } /* bigUIConv */
> > > > > ----------------------------------------
>
> > > > > If you add it at the end of the file big_gmp.c you should
> > > > > succeed.
>
> > > > > I hope that helps. Sorry for the trouble.
>
> > > > Thanks! That fixed it.
>
> > > > Hate to be a pest, but I've got three different machines with
> > > > three different cygwin configurations. I try my best to resolve
> > > > things, but compilers aren't my forte. I even considered trying
> > > > to find the missing reference, but I can see that I never would
> > > > have resolved it.
>
> > > > > If there are other problems: Please tell me.
>
> > > > I haven't had time to run it yet, but I plan to use the gmp
> > > > version when I do a Seed7 implementation of Sedgewick's
> > > > algorithm and we don't want my C version to have an unfair
> > > > advantage.
>
> > > Can you give me an update.
>
> > Trying to convert Sedgewick algorithm from C
> > to Seed7.
>
> > Quick question. I define an empty array using
>
> > * var array cycle: cycle_stats is 0 times cycle.value
>
> > and then expand it one index at a time as needed by
>
> > * cycle_stats &:= [](attractor_stats)
>
> This is possible, but it costs time to extend the array.

I expected that. I only do it sporadically 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:
>
> * cycle_stats := 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:
>
> * cycle_stats &:= 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
>
> > * 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:
>
> * var array cycle: cycle_stats is 0 times cycle.value;
>
> and use the statement
>
> * cycle_stats := 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. 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 := 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 support (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)
> > * * * * *efd.py * * * (Brent)
> > * * * * *ecd001.sd7 * (Brent) old Seed7
> > * * * * *ecd001.sd7 * (Brent) current Seed7 with GMP
> > * * * * *ecd001.sd7 * (Brent) current Seed7 without GMP
> > * * * * *ccd020.c * * (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. What I want is a documentary
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).

I think when all the tradeoffs are considered, everything will
come out looking good.

>
>
>
>
>
> > Oh, and this cycle detection is one place where GMP
> > makes it worse (68 sec), not better. Yet GMP outperforms
> > Seed7 bigIntegers in the Collatz test of large Mersenne
> > numbers. Excessive overhead in setting up the mpz's
> > using up the time savings, so it depends on ratio
> > of variables to operations?
>
> > Anyway, I'm still trying to collate the big picture.
>
> > > What should I add to the next release (except for a faster
> > > modInverse function)?
>
> > I haven't given it much thought.
>
> > > BTW.: What results does mpz_invert(rop, op1, op2) have when
> > > op2 is negative?
>
> > Same as positive, apparently.
>
> > >>> import gmpy
> > >>> gmpy.invert(8,9)
> > mpz(8)
> > >>> gmpy.invert(8,-9)
> > mpz(8)
> > >>> for j in xrange(1,10):
>
> > * * * * for i in xrange(2,10):
> > * * * * * * * * print gmpy.invert(j,i),
> > * * * * print
> > 1 1 1 1 1 1 1 1
> > 0 2 0 3 0 4 0 5
> > 1 0 3 2 0 5 3 0
> > 0 1 0 4 0 2 0 7
> > 1 2 1 0 5 3 5 2
> > 0 0 0 1 0 6 0 0
> > 1 1 3 3 1 0 7 4
> > 0 2 0 2 0 1 0 8
> > 1 0 1 4 0 4 1 0
>
> > >>> for j in xrange(1,10):
>
> > * * * * for i in xrange(-2,-10,-1):
> > * * * * * * * * print gmpy.invert(j,i),
> > * * * * print
> > 1 1 1 1 1 1 1 1
> > 0 2 0 3 0 4 0 5
> > 1 0 3 2 0 5 3 0
> > 0 1 0 4 0 2 0 7
> > 1 2 1 0 5 3 5 2
> > 0 0 0 1 0 6 0 0
> > 1 1 3 3 1 0 7 4
> > 0 2 0 2 0 1 0 8
> > 1 0 1 4 0 4 1 0
>
> > The gmpy help says just that it not be zero:
>
> > Help on built-in function invert in module gmpy:
>
> > invert(...)
> > * * invert(x,m): returns the inverse of x modulo m, i.e.,
> > * * that y such that x*y==1 modulo m, or 0 if no such
> > * * y exists.
> > * * m must be an ordinary Python int, !=0;
> > * * x must be an mpz, or else gets converted to one.
>
> > The GNU GMP manual says:
>
> > int mpz_invert (mpz t rop, mpz t op1, mpz t op2) [Function]
> > * Compute the inverse of op1 modulo op2 and
> > * put the result in rop. If the inverse exists,
> > * the return value is non-zero and rop will satisfy
> > * 0 <= rop < op2. If an inverse doesn’t exist the
> > * return value is zero and rop is undefined
>
> > > Is it defined at all?
>
> > Well, it doesn't say you CAN'T use negative operands.
> > Does "rop will satisfy 0 <= rop < op2" mean that rop
> > COULD be negative? Seems rather ambiguous to me.
>
> That is also my impression.
>
> > Of course, the above test is in Python, it MIGHT be
> > different in C. For example, the linear congruence
> > solver divm() is not a GMP function. It is a value-added
> > feature of the gmpy wrapper of GMP. In divm(), "not
> > invertable" throws an exception although a direct call
> > to invert() does not, it simply returns 0.
>
> Thank you for the information.
>
> 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.

On 25 Apr., 19:30, Mensanator wrote:
> On Apr 25, 7:01 am, thomas.mer...@gmx.at wrote:
> > On 25 Apr., 09:46, Mensanator wrote:
> > > On Apr 25, 1:30 am, thomas.mer...@gmx.at wrote:
> > > > Can you give me an update.
>
> > > Trying to convert Sedgewick algorithm from C
> > > to Seed7.
>
> > > Quick question. I define an empty array using
>
> > > var array cycle: cycle_stats is 0 times cycle.value
>
> > > and then expand it one index at a time as needed by
>
> > > cycle_stats &:= [](attractor_stats)
>
> > This is possible, but it costs time to extend the array.
>
> I expected that. I only do it sporadically 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:
>
> > cycle_stats := 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:
>
> > cycle_stats &:= 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
>
> > > 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:
>
> > var array cycle: cycle_stats is 0 times cycle.value;
>
> > and use the statement
>
> > cycle_stats := 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 thrashing?

> 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 := 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 support (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)
> > > efd.py (Brent)
> > > ecd001.sd7 (Brent) old Seed7
> > > ecd001.sd7 (Brent) current Seed7 with GMP
> > > ecd001.sd7 (Brent) current Seed7 without GMP
> > > ccd020.c (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.

> What I want is a documentary
> 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: 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.

On Apr 27, 8:58*am, thomas.mer...@gmx.at wrote:
> On 25 Apr., 19:30, Mensanator wrote:
>
>
>
>
>
> > On Apr 25, 7:01 am, thomas.mer...@gmx.at wrote:
> > > On 25 Apr., 09:46, Mensanator wrote:
> > > > On Apr 25, 1:30 am, thomas.mer...@gmx.at wrote:
> > > > > Can you give me an update.
>
> > > > Trying to convert Sedgewick algorithm from C
> > > > to Seed7.
>
> > > > Quick question. I define an empty array using
>
> > > > * var array cycle: cycle_stats is 0 times cycle.value
>
> > > > and then expand it one index at a time as needed by
>
> > > > * cycle_stats &:= [](attractor_stats)
>
> > > This is possible, but it costs time to extend the array.
>
> > I expected that. I only do it sporadically 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:
>
> > > * cycle_stats := 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:
>
> > > * cycle_stats &:= 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
>
> > > > * 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:
>
> > > * var array cycle: cycle_stats is 0 times cycle.value;
>
> > > and use the statement
>
> > > * cycle_stats := 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 thrashing?

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=85085, 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=85085.

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 := 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 support (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)
> > > > * * * * *efd.py * * * (Brent)
> > > > * * * * *ecd001.sd7 * (Brent) old Seed7
> > > > * * * * *ecd001.sd7 * (Brent) current Seed7 with GMP
> > > > * * * * *ecd001.sd7 * (Brent) current Seed7 without GMP
> > > > * * * * *ccd020.c * * (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 documentary
> > 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: *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.- Hide quoted text -
>
> - Show quoted text -- Hide quoted text -
>
> - Show quoted text -

I couldn't find anywhere in the manual how to stop the program.

Is there an equivalent to C's exit(0)?




Also, am I reading this correctly?

A[1] => First element,

You have arrays index from 1?

That's insane.

Why would you do such a silly thing?

How much time do you waste translating this to C?

Haven't you ever used modular arithmetic with indices,
where 0 is a legal value?

This is serious enough not to recommend Seed7 for
"real" programming.

On 28 Apr., 01:30, Mensanator wrote:
> I couldn't find anywhere in the manual how to stop the program.
>
> Is there an equivalent to C's exit(0)?

There is the function:
exit (PROGRAM)

where 'PROGRAM' is used as keyword. Currently I have no possibility
to provide a return value for exit. I will look at that. Probably
the best solution is to provide an 'exit' function with an integer
parameter just as C has.

> Also, am I reading this correctly?
>
> A[1] => First element,
>
> You have arrays index from 1?

This is the default. But the lowest allowed index of an array is
just as dynamic as the highest allowed index is. If you define an
array with:

var array integer: arr is 0 times 0;

The starting index is 1. If you assign a new value to this array
with

arr := [0] (1, 2, 3);

it gets a new starting index, a new size and new values for arr[0],
arr[1] and arr[2]. Now a statement as

writeln(arr[0]);

writes 1. There is no limitation what value can be used as the
first index for an array. You can define the following array:

var array integer: arr2 is [-2] (3, 4, 5, 6);

Now 'writeln(arr2[-1]);' writes 4.
To solve your problem you need to replace

cycle_stats := number times cycle.value;

with

cycle_stats := [0 .. number] times cycle.value;

to allow idices in the range 0 to number. If you want a C like
behavior where the array has number elements counting from
0 to number -1 use:

cycle_stats := [0 .. pred(number)] times cycle.value;

If you add elements to the array with:

cycle_stats &:= 1000 times cycle.value;

the lowest array index (0 in this case) stays unchanged.
I hope that this helps.

It seems that I need to add something to the manual and the FAQ.

BTW.: Seed7 does also support not integer indices. You can also
define arrays with use 'char', 'boolean' or some enumeration type
as index.

> That's insane.
>
> Why would you do such a silly thing?

To explain why I use 1 as default start index for arrays I provide
a little list:

- apple
- cherry
- lemon
- strawberry
- pear
- orange

Most people agree that the third line from below is 'strawberry'.
In normal life nobody would say that the second line from the top is
'lemon'. So Seed7 uses 'common sense' as guideline instead of
'computer science wisdom'.

> How much time do you waste translating this to C?

You are probably speaking of runtime overhead.
There is some overhead. For every array access an additional
subtraction is necessary. But Seed7 checks also that
index >= upper_bound and index <= lower_bound which is probably
more expensive than a subtraction.

> Haven't you ever used modular arithmetic with indices,
> where 0 is a legal value?
>
> This is serious enough not to recommend Seed7 for
> "real" programming.

Sorry that you had troubles with the arrays. Mea culpa. I should
improve the chapter about arrays in the manual. I hope that

cycle_stats := [0 .. number] times cycle.value;

solves your problem. If you still have problems or have more
questions, just ask.

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.

On Apr 28, 3:19*am, thomas.mer...@gmx.at wrote:
> On 28 Apr., 01:30, Mensanator wrote:
>
> > I couldn't find anywhere in the manual how to stop the program.
>
> > Is there an equivalent to C's exit(0)?
>
> There is the function:
> * exit (PROGRAM)
>
> where 'PROGRAM' is used as keyword. Currently I have no possibility
> to provide a return value for exit. I will look at that. Probably
> the best solution is to provide an 'exit' function with an integer
> parameter just as C has.

Oh, I don't need the parameter, just the way out. And it worked fine,
just what I needed (to abort if user doesn't supply all the required
command line parameters). I searched for "exit" in the manual and
didn't
find it. If this isn't in the manual, it should be.

>
> > Also, am I reading this correctly?
>
> > *A[1] => First element,
>
> > You have arrays index from 1?
>
> This is the default. But the lowest allowed index of an array is
> just as dynamic as the highest allowed index is. If you define an
> array with:
>
> * var array integer: arr is 0 times 0;
>
> The starting index is 1. If you assign a new value to this array
> with
>
> * arr := [0] (1, 2, 3);
>
> it gets a new starting index, a new size and new values for arr[0],
> arr[1] and arr[2]. Now a statement as
>
> * writeln(arr[0]);
>
> writes 1. There is no limitation what value can be used as the
> first index for an array. You can define the following array:
>
> * var array integer: arr2 is [-2] (3, 4, 5, 6);
>
> Now 'writeln(arr2[-1]);' writes 4.
> To solve your problem you need to replace
>
> * cycle_stats := number times cycle.value;
>
> with
>
> * cycle_stats := [0 .. number] times cycle.value;
>
> to allow idices in the range 0 to number. If you want a C like
> behavior where the array has number elements counting from
> 0 to number -1 use:
>
> * cycle_stats := [0 .. pred(number)] times cycle.value;
>
> If you add elements to the array with:
>
> * cycle_stats &:= 1000 times cycle.value;
>
> the lowest array index (0 in this case) stays unchanged.
> I hope that this helps.

Oh, ok. I take back what I said about Seed7 being worthless.

>
> It seems that I need to add something to the manual and the FAQ.

Yes, you should. Otherwise you risk pissing off potential users
who have to manipulate their array pointers because you didn't
document that it's a default and can be changed.

>
> BTW.: Seed7 does also support not integer indices. You can also
> define arrays with use 'char', 'boolean' or some enumeration type
> as index.
>
> > That's insane.
>
> > Why would you do such a silly thing?
>
> To explain why I use 1 as default start index for arrays I provide
> a little list:
>
> * - apple
> * - cherry
> * - lemon
> * - strawberry
> * - pear
> * - orange
>
> Most people agree that the third line from below is 'strawberry'.

But then, most people aren't programmers. Who's your target audience
for Seed7?

> In normal life nobody would say that the second line from the top is
> 'lemon'. So Seed7 uses 'common sense' as guideline instead of
> 'computer science wisdom'.

Suppose I'm doing math in radix 666 and have an array representing
the digit positions:

'123'
'444'
'23'

To evaluate this, I would do 23*666**2 + 444*666**1 + 123*666**0.

So the array must index from 0.

You'll get a lot further using 'computer science wisdom' than with
'common sense'. I always ask people:

"Do you want the Truth or something you can understand?"

Ignorance is only skin deep, but stupid goes to the bone.

>
> > How much time do you waste translating this to C?
>
> You are probably speaking of runtime overhead.
> There is some overhead. For every array access an additional
> subtraction is necessary. But Seed7 checks also that
> index >= upper_bound and index <= lower_bound which is probably
> more expensive than a subtraction.

Ok, it least it crashes gracefully instead of getting a segment fault.

>
> > Haven't you ever used modular arithmetic with indices,
> > where 0 is a legal value?
>
> > This is serious enough not to recommend Seed7 for
> > "real" programming.
>
> Sorry that you had troubles with the arrays. Mea culpa. I should
> improve the chapter about arrays in the manual. I hope that
>
> * cycle_stats := [0 .. number] times cycle.value;
>
> solves your problem. If you still have problems or have more
> questions, just ask.

Well, it was easy enough to work around, so I'll leave it as is.

Oh, and I think I got the Sedgewick algorithm working now in Seed7.

If it passes my testing, I'll post it on my web-site tonight
in case you want a peek before I have the web page that will
highlight the Seed7 versions of the Brent & Sedgewick algorithms.

>
> 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.

On Apr 28, 4:15�pm, Mensanator wrote:

>
> If it passes my testing, I'll post it on my web-site tonight
> in case you want a peek before I have the web page that will
> highlight the Seed7 versions of the Brent & Sedgewick algorithms.
>

The web page has been completed and everything uploaded!

You can see it at



Inside there are links to the Seed7 versions of
Brent's algorithm and Sedgewick's algorithm.

Sometime tomorrow I'll make a post to sci.math
announcing my new Collatz Conjecture comic book.

On 3 Mai, 09:43, Mensanator wrote:
> On Apr 28, 4:15�pm, Mensanator wrote:
>
> > If it passes my testing, I'll post it on my web-site tonight
> > in case you want a peek before I have the web page that will
> > highlight the Seed7 versions of the Brent & Sedgewick algorithms.
>
> The web page has been completed and everything uploaded!
>
> You can see it at
>
>

It looks very good. How is it linked from your homepage?

> Inside there are links to the Seed7 versions of
> Brent's algorithm and Sedgewick's algorithm.

Great. Thanks a lot for your effort. I will add a link to your
web page to the Seed7 homepage.

BTW. Currently I moved my focus away from bigInteger's,
but if you think that some function / feature is still needed
I will look at it.

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.

On 7 Mai, 09:48, thomas.mer...@gmx.at wrote:
> On 3 Mai, 09:43, Mensanator wrote:
>
> > On Apr 28, 4:15�pm, Mensanator wrote:
>
> > > If it passes my testing, I'll post it on my web-site tonight
> > > in case you want a peek before I have the web page that will
> > > highlight the Seed7 versions of the Brent & Sedgewick algorithms.
>
> > The web page has been completed and everything uploaded!
>
> > You can see it at
>
> >
>
> It looks very good. How is it linked from your homepage?

Now I found the link at your homepage.
I must have been blind...

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.

On May 7, 3:24Â*am, thomas.mer...@gmx.at wrote:
> On 7 Mai, 09:48, thomas.mer...@gmx.at wrote:
>
> > On 3 Mai, 09:43, Mensanator wrote:
>
> > > On Apr 28, 4:15�pm, Mensanator wrote:
>
> > > > If it passes my testing, I'll post it on my web-site tonight
> > > > in case you want a peek before I have the web page that will
> > > > highlight the Seed7 versions of the Brent & Sedgewick algorithms.
>
> > > The web page has been completed and everything uploaded!
>
> > > You can see it at
>
> > >
>
> > It looks very good. How is it linked from your homepage?
>
> Now I found the link at your homepage.
> I must have been blind...

It might not have been there the first time you looked
as there was a slight lag in getting the Home Page updated.

I can't think of anything about bigIntegers at the moment.

I, too, have moved on to another project. If I ever get the
theory worked out, I may do the algorithm in Seed7 for performance.

If I encounter any problems, I'll let you know.

>
> 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.