On Apr 25, 7:01=A0am, 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:
> > > On 22 Apr., 19:09, Mensanator <mensana...@[EMAIL PROTECTED]
> wrote:
> > > > On Apr 22, 1:46 am, thomas.mer...@[EMAIL PROTECTED]
wrote:
> > > > > On 22 Apr., 06:26, Mensanator <mensana...@[EMAIL PROTECTED]
> wrote:
> > > > > > On Apr 20, 3:51 pm, thomas.mer...@[EMAIL PROTECTED]
wrote:
> > > > > > > - The file read_me.txt was improved to contain a chapter
about=
> > > > > > > =A0 warnings and a chapter which explains how to use the GMP
l=
ibrary.
>
> > > > > > I'm having problems with this (regular bigInt compiled fine).
>
> > > > > > I'm using cygwin and modified the makefile thusly:
>
> > > > > > # LIBS =3D c:/cygwin/usr/X11R6/lib/libX11.dll.a -lncurses -lm
> > > > > > LIBS =3D c:/cygwin/usr/X11R6/lib/libX11.dll.a -lncurses -lm
C:/c=
ygwin/
> > > > > > Seed7/seed7/lib/libgmp.a
> > > > > > SEED7_LIB =3D seed7_05.a
> > > > > > COMP_DATA_LIB =3D s7_data.a
> > > > > > COMPILER_LIB =3D s7_comp.a
> > > > > > CC =3D gcc
>
> > > > > > # BIGINT =3D big_rtl
> > > > > > BIGINT =3D big_gmp
>
> > > > > > I had to use a full path for my gmp library which is libgmp.a
li=
ke 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 =A0hi.o s7_comp.a s7_data.a seed7_05.a
c:/cygwin/usr/X11R6/l=
ib/
> > > > > > 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
referenc=
e to
> > > > > > `_bigUIConv'
> > > > > > seed7_05.a(fil_rtl.o):fil_rtl.c:(.text+0x11d): undefined
referen=
ce to
> > > > > > `_bigUIConv'
> > > > > > Info: resolving _cur_term by linking to __imp__cur_term
(auto-im=
****t)
> > > > > > 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
>
> > > > > =A0 {
> > > > > =A0 =A0 gmpBiginttype result;
>
> > > > > =A0 /* bigUIConv */
> > > > > =A0 =A0 result =3D malloc(sizeof(__mpz_struct));
> > > > > =A0 =A0 mpz_init_set_ui(result, number);
> > > > > =A0 =A0 return(result);
> > > > > =A0 } /* 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
>
> > =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. 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. 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).
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.
>
> > >>> im****t gmpy
> > >>> gmpy.invert(8,9)
> > mpz(8)
> > >>> gmpy.invert(8,-9)
> > mpz(8)
> > >>> for j in xrange(1,10):
>
> > =A0 =A0 =A0 =A0 for i in xrange(2,10):
> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 print gmpy.invert(j,i),
> > =A0 =A0 =A0 =A0 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):
>
> > =A0 =A0 =A0 =A0 for i in xrange(-2,-10,-1):
> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 print gmpy.invert(j,i),
> > =A0 =A0 =A0 =A0 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(...)
> > =A0 =A0 invert(x,m): returns the inverse of x modulo m, i.e.,
> > =A0 =A0 that y such that x*y=3D=3D1 modulo m, or 0 if no such
> > =A0 =A0 y exists.
> > =A0 =A0 m must be an ordinary Python int, !=3D0;
> > =A0 =A0 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]
> > =A0 Compute the inverse of op1 modulo op2 and
> > =A0 put the result in rop. If the inverse exists,
> > =A0 the return value is non-zero and rop will satisfy
> > =A0 0 <=3D rop < op2. If an inverse doesn=92t exist the
> > =A0 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 <=3D 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: =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.
|
