Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #57445 > unrolled thread

Re: string-stack.4th

Back to article view | Back to comp.lang.forth

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-16 08:23 -0700
    Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-16 08:33 -0700
      Re: string-stack.4th "Rudy Velthuis" <newsgroups@rvelthuis.de> - 2017-04-16 22:34 +0000
        Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-16 17:11 -0700
          Re: string-stack.4th "Rudy Velthuis" <newsgroups@rvelthuis.de> - 2017-04-17 23:22 +0000
            Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-17 18:14 -0700
              Re: string-stack.4th hughaguilar96@gmail.com - 2017-04-17 18:44 -0700
              Re: string-stack.4th "Rudy Velthuis" <newsgroups@rvelthuis.de> - 2017-04-19 23:09 +0000
    Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-16 09:02 -0700
      Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-16 15:29 -0700
      Re: string-stack.4th hughaguilar96@gmail.com - 2017-04-16 19:43 -0700
        Re: string-stack.4th hughaguilar96@gmail.com - 2017-04-16 22:42 -0700
          Re: string-stack.4th hughaguilar96@gmail.com - 2017-04-16 23:09 -0700
            Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-16 23:34 -0700
              Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-17 00:15 -0700
              Re: string-stack.4th Paul Rubin <no.email@nospam.invalid> - 2017-04-17 01:19 -0700
                Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-17 02:06 -0700
                  Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-17 02:50 -0700
                  Re: string-stack.4th Paul Rubin <no.email@nospam.invalid> - 2017-04-17 13:14 -0700
                    Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-17 15:58 -0700
                      Re: string-stack.4th Paul Rubin <no.email@nospam.invalid> - 2017-04-17 16:57 -0700
                        Re: string-stack.4th "Elizabeth D. Rather" <erather@forth.com> - 2017-04-17 15:07 -1000
                        Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-05-17 05:32 -0700
                      Re: string-stack.4th hughaguilar96@gmail.com - 2017-04-17 19:49 -0700
                Re: string-stack.4th "David N. Williams" <williams@umich.edu> - 2017-04-17 20:11 -0500
                  Re: string-stack.4th Paul Rubin <no.email@nospam.invalid> - 2017-04-17 18:15 -0700
                  Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-17 19:13 -0700
                    Re: string-stack.4th Paul Rubin <no.email@nospam.invalid> - 2017-04-17 19:21 -0700
                      Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-18 01:25 -0700
                        Re: string-stack.4th Paul Rubin <no.email@nospam.invalid> - 2017-04-18 19:27 -0700
                      Re: string-stack.4th "David N. Williams" <williams@umich.edu> - 2017-04-18 11:27 -0500
                  Re: string-stack.4th mhx@iae.nl - 2017-04-18 11:53 -0700
                    Re: string-stack.4th albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-04-20 20:48 +0200
                      Re: string-stack.4th mhx@iae.nl - 2017-04-20 14:58 -0700
            Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-17 00:46 -0700
    Re: string-stack.4th hughaguilar96@gmail.com - 2017-04-16 19:31 -0700

Page 2 of 2 — ← Prev page 1 [2]

#57513

lehs <skydda.barnen@gmail.com> writes:
> GForth Android runs on 1.6 GHz Rockchip RK3066
> The others on 1.6 GHz Celeron both dual core. 

Pretty good.  On the original IBM PC, with a C implementation, this
calculation apparently would have taken minutes.

> I've no idea how to code public-key cryptography or why I would need it.

Basically say I want to send you a secret message.  You pick two random
primes p and q and compute the product N=pq and send me N.  Other people
(including me) can't find p and q from N, under the assumption that
factoring numbers of this size is computationally intractable.  Now you
figure out the totient phi(N)=(p-1)*(q-1), which is the size of Z*(N),
the group of numbers coprime to N.  Since you can find p and q from
phi(N), that means finding phi(N) is as hard as factoring, so N won't
leak info about phi(N) more than it does about the factors.

Now use the extended Euclidean algorithm to find a number d such that
d*3 == 1 (mod phi(N)) and keep d secret.  I take my message M and send
you M**3 mod N.  You use d to find M**(3*d) mod N, but since 3*d-1 is
a multiple of phi(N),  that means that M**(3*d) mod N is just M.

So without telling me anything secret, on a channel where anyone can be
listening, you've sent me info that lets me send you an encrypted
message.  This is public-key cryptography and the above algorithm is
called "RSA" after its inventors Rivest, Shamir, and Adelman.

Obviously there are a lot of practical details glossed over above, but
basically it's all about how fast you can do modular exponentials in a
group of size around 2**1000.  That's why I wanted that timing.

[toc] | [prev] | [next] | [standalone]

#57515

On 4/17/17 1:57 PM, Paul Rubin wrote:
> lehs <skydda.barnen@gmail.com> writes:
>> GForth Android runs on 1.6 GHz Rockchip RK3066
>> The others on 1.6 GHz Celeron both dual core.
>
> Pretty good.  On the original IBM PC, with a C implementation, this
> calculation apparently would have taken minutes.
>
>> I've no idea how to code public-key cryptography or why I would need it.
>
> Basically say I want to send you a secret message.  You pick two random
> primes p and q and compute the product N=pq and send me N.  Other people
> (including me) can't find p and q from N, under the assumption that
> factoring numbers of this size is computationally intractable.  Now you
> figure out the totient phi(N)=(p-1)*(q-1), which is the size of Z*(N),
> the group of numbers coprime to N.  Since you can find p and q from
> phi(N), that means finding phi(N) is as hard as factoring, so N won't
> leak info about phi(N) more than it does about the factors.
>
> Now use the extended Euclidean algorithm to find a number d such that
> d*3 == 1 (mod phi(N)) and keep d secret.  I take my message M and send
> you M**3 mod N.  You use d to find M**(3*d) mod N, but since 3*d-1 is
> a multiple of phi(N),  that means that M**(3*d) mod N is just M.
>
> So without telling me anything secret, on a channel where anyone can be
> listening, you've sent me info that lets me send you an encrypted
> message.  This is public-key cryptography and the above algorithm is
> called "RSA" after its inventors Rivest, Shamir, and Adelman.
>
> Obviously there are a lot of practical details glossed over above, but
> basically it's all about how fast you can do modular exponentials in a
> group of size around 2**1000.  That's why I wanted that timing.

Versions were implemented by FORTH, Inc. and MPE for the Europay project 
in the 90's, for processing smart card transations. On an 8051 (which 
was used in some of the terminals we programmed) it took some seconds 
(maybe 20-30, but it feels like an eternity). Nowadays smart card 
terminals are proliferating in the US, and I marvel at how slow some of 
them are: that algorithm is exactly what is taking all the time. The 
terminals we programmed in Forth in the 90's were faster than most of 
the ones we see in stores.

Cheers,
Elizabeth

-- 
Elizabeth D. Rather
FORTH, Inc.
6080 Center Drive, Suite 600
Los Angeles, CA  90045
USA

[toc] | [prev] | [next] | [standalone]

#59427

Den tisdag 18 april 2017 kl. 01:57:45 UTC+2 skrev Paul Rubin:
> lehs <skydda.barnen@gmail.com> writes:
> > GForth Android runs on 1.6 GHz Rockchip RK3066
> > The others on 1.6 GHz Celeron both dual core. 
> 
> Pretty good.  On the original IBM PC, with a C implementation, this
> calculation apparently would have taken minutes.
> 
> > I've no idea how to code public-key cryptography or why I would need it.
> 
> Basically say I want to send you a secret message.  You pick two random
> primes p and q and compute the product N=pq and send me N.  Other people
> (including me) can't find p and q from N, under the assumption that
> factoring numbers of this size is computationally intractable.  Now you
> figure out the totient phi(N)=(p-1)*(q-1), which is the size of Z*(N),
> the group of numbers coprime to N.  Since you can find p and q from
> phi(N), that means finding phi(N) is as hard as factoring, so N won't
> leak info about phi(N) more than it does about the factors.
> 
> Now use the extended Euclidean algorithm to find a number d such that
> d*3 == 1 (mod phi(N)) and keep d secret.  I take my message M and send
> you M**3 mod N.  You use d to find M**(3*d) mod N, but since 3*d-1 is
> a multiple of phi(N),  that means that M**(3*d) mod N is just M.
> 
> So without telling me anything secret, on a channel where anyone can be
> listening, you've sent me info that lets me send you an encrypted
> message.  This is public-key cryptography and the above algorithm is
> called "RSA" after its inventors Rivest, Shamir, and Adelman.
> 
> Obviously there are a lot of practical details glossed over above, but
> basically it's all about how fast you can do modular exponentials in a
> group of size around 2**1000.  That's why I wanted that timing.

Thanks for the explanation! I've tried to implement this with bigintegers. Occasionally encrypt_string and decrypt_string works but sometimes it fails. I will find out why and define words encrypt_file and decrypt_file. However, I don't think it works very fast, a 1Mbyte file would take minutes to encrypts and more to decrypt. But the surprising time thief is getkeys, which find the two big primes, calculates Phi(N) and the private_key. I guess that INVMOD is the problem.


https://github.com/Lehs/ANS-Forth-libraries

[toc] | [prev] | [next] | [standalone]

#57528

On Monday, April 17, 2017 at 4:18:43 PM UTC-7, Rudy Velthuis wrote:
> hughaguilar96@gmail.com wrote:
> 
> > > > No, of course not. Then you use c-addr u, like in other languages.
> > > 
> > > So that's why we have c-addr u.
> 
> I understand the need for c-addr u in certain situations, but it is IMO
> not a good idea to always having to supply the u. Only supply it where
> it is needed.
>  
> > Rudy Velthuis doesn't know what he is talking about. Consumers work
> > fine with derivative strings;
> 
> Rudy Velthuis does know what he is talking about. He is just not so
> familiar with current affairs in Forth yet and wonders why certain
> things are done the way they are currently done, in Forth.
> 
> I don't quite know what you mean with "derivative strings" though. 

You don't know what you are talking about when you criticize my STRING-STACK.4TH for not using COW --- it does use COW --- that is the whole point.

A "unique" string is on the heap. A "derivative" string is a reference to another string, either a unique or a non-mutable (such as came from S").

The consumers (such as with .$ DROP$ etc.) will FREE the string afterward if it unique, but will first convert any derivatives of that string into uniques (involves calling ALLOCATE and copying the string). Whether it is unique or derivative it gets dropped from the string-stack. I have a lot of functions for searching strings, and these are all consumers.

The modifiers (such as REVERSE$ etc.) change a string. If the string is unique, they first search the string-stack for any derivatives of this string and convert them into uniques (involves calling ALLOCATE and copying the string). If the string is derivative, they first convert the string into a unique (involves calling ALLOCATE and copying the string). 

My string-concatenation function +$ was one of the most complicated functions I've written in quite some time. It was complicated because there are two parameters, and each parameter can be either unique or derivative, so there are 4 permutations of kinds of strings being concatenated. 

I have a lot of functions for finding substrings. These are not modifiers. They produce a derivative string whose address is inside of the unique string. If that unique later gets modified or consumed, they are found on the string-stack and determined to be derivatives of that string, so they get converted into uniques at that time.

The stack jugglers (such as SWAP$ ROT$ etc.) just move around the items on the string-stack without concern as to them being unique or derivative. The duplicators (such as DUP$ OVER$ etc.) made a derivative string (doesn't matter if the string being duplicated was a unique or a derivative).

Notice that when DUP$ OVER$ etc. are used, you end up with a derivative on the stack and the unique that it is derived from underneath. This is a good thing! If you then consume that string, it is very efficient, because consuming a derivative is efficient (no need to mess with the heap). Here is an example:

empty$  ok
s" abcdefgh" >$  dup$ .$ abcdefgh ok
.s$ 
STRING STACK:
derivative: |abcdefgh| ok

The DUP$ just made a derivative, and then .$ consumed it. The original string (which was a derivative of the non-mutable S" string given to >$) is still on the stack.

Here is another example:

empty$  ok
s" abcdefgh" >$  s" FGH" >$ isuffix$  ok-1 
. -1  ok
.s$ 
STRING STACK:
derivative: |fgh|
derivative: |abcdefgh| ok

The top value of the string-stack (the |fgh| string) is a derivative of the second value of the string-stack (the |abcdefgh| string) --- it is inside of that string that it is derived from.

Here is another example (this one useful enough that I made it into a function and put it in the package):

: maybe-extract$ ( -- extracted? )                              \ string: a b -- str        \ extract B from A if possible
    2dup$ swap$ find$  dup -1 = if  drop  drop$  false exit then                            \ drop the -1, DROP$ B and return A with a false flag
    len$ anti-mid$ 
    true ;

\ MAYBE-EXTRACT returns TRUE if it could extract B from A, and it returns STR which is A with B extracted from it.
\ If it couldn't, then it returns FALSE and it returns STR as A unchanged.

Here is a test:

empty$  ok
s" abcdefgh" >$  s" DEF" >$ maybe-extract$  ok-1 
. -1  ok
.s$ 
STRING STACK:
unique:     |abcgh| ok
empty$  ok
s" abcdefgh" >$  s" XYZ" >$ maybe-extract$  ok-1 
. 0  ok
.s$ 
STRING STACK:
derivative: |abcdefgh| ok

Note that here, when we find the string and extract it, the new string is a unique because it has been modified (it had the substring extracted from it).

> And where I come from, strings are often modified, e.g. concatenated,
> replaced, searched, etc. They often have a life that is a little bit
> longer than what could be found in the current input buffer or other
> volatile storate.
> 
> I assume this is not the case in most Forth code? Or are such strings
> generally compiled into a definition or stored in a variable, meaning
> they are copied after all?

Most Forth code is crap.

Every time that I write any ANS-Forth code, I help to kill ANS-Forth. This STRING-STACK.4TH is a typical example. By writing it I induced Anton Ertl to step forward and defend Elizabeth Rather's idiotic scheme of holding strings in global variables (the <# #> pad, the S" pad, and PAD) --- he makes himself look like an idiot by doing this --- it is obvious that he does this because Elizabeth Rather appointed him to the Forth-200x committee and he is obliged to defend all of her design decisions in ANS-Forth, not matter how idiotic.

[toc] | [prev] | [next] | [standalone]

#57516

On 4/17/17 3:19 AM, Paul Rubin wrote:
 > lehs <skydda.barnen@gmail.com> writes:
 >> I might be able to speed up my bigintegers.4th
 >
 > I wonder if you could run a test for me: let p = 17**250 + 2704
 > (this number happens to be prime) and time how long it takes for
 > your implementation to do a Fermat test: calculate (3**p) mod p
 > which should be equal to 3.
 >
 > My feeling is that if this takes less than a few seconds, your package
 > is reasonably usable for public-key cryptography.

Out of curiosity, I tried this with the integer part of my forth-gmpfr
package, which has a garbage collected bignum stack in ANS Forth, with
bindings to the GNU Multiple Precision library:

   http://www.umich.edu/~williams/archive/forth/gmpfr/

I used pfe for the timings.  In the file names 3^p_mod_p_xxx.fs below,
"xxx" indicates the number of trials.  The trials were run on a MacBook
Pro 2.2 GHz Intel Core i7 (4 cores) under macOS Sierra 10.12.4.  The
gmpfr package and GNU libraries used haven't been changed since January,
2012.

[haag:~/gmpfr] dnwills% /usr/bin/time -p pfe -q -y 3^p_mod_p_100.fs
real         0.32
user         0.31
sys          0.00
[haag:~/gmpfr] dnwills% /usr/bin/time -p pfe -q -y 3^p_mod_p_200.fs
real         0.70
user         0.69
sys          0.00
[haag:~/gmpfr] dnwills% /usr/bin/time -p pfe -q -y 3^p_mod_p_1000.fs
real         2.95
user         2.94
sys          0.00

So the user time for one calculation is less than 3 milliseconds.  I
don't know how much of that is bignum stack overhead, compared to the
GNU library calls.

Here's the 1000-trial code:

3^p_mod_p_1000.fs
-----------------
\  Title:   GMPFR Benchmark for (3**p) mod p with a large prime p
\   File:   3^p_mod_p_1000.fs
\  Author:  David N. Williams
\    Date:  April 17, 2017
\ License:  public domain

\ To run with pfe:
\   /usr/bin/time -p pfe -q -y 3^p_mod_p_1000.fs

true constant MULTI-INTEGERS
s" gmpfr.fs" INCLUDED
17 u>b 250 b^u 2704 bu+ bconstant p

: tries  ( n -- )
   0 DO
     3 u>b p p b-pow-mod  \ 3^p mod p
     bdrop
     \ b.
   LOOP
;

1000 tries
bye
-----------------

Here are some checks (long result broken into lines):

p b. 40947778423540104959067988292528857405972603447195632195037
8594747292053767136408255971273136413908600752651227962494772762
1804563995511385846512375859465262648854834054706258499178583491
6459459029262407818318245524277482110372262457010816382213629216
030118638993632313978231084140883786669390389605436763953 ok
3 u>b p p b-pow-mod b. 3 ok

I haven't tested whether the value of p above is correct, but at least
it's big, odd, and produces 3 in the calculation.

-- David W.

[toc] | [prev] | [next] | [standalone]

#57518

"David N. Williams" <williams@umich.edu> writes:
> So the user time for one calculation is less than 3 milliseconds.

Cool.  Yes, GMP is very highly optimized, both in terms of using fancy
specialized algorithms for the modexp (e.g. Montgomery reduction), and
in using carefully tuned assembly code to get max performance from the
machine arithmetic.  I didn't even mention GMP in my post because
there's no way to expect a pure Forth implementation to come anywhere
near it.  I just wanted to know whether the Forth version was fast
enough to be useful at all, which it is.

[toc] | [prev] | [next] | [standalone]

#57523

Den tisdag 18 april 2017 kl. 03:11:53 UTC+2 skrev David N. Williams:
> On 4/17/17 3:19 AM, Paul Rubin wrote:
>  > lehs <skydda.barnen@gmail.com> writes:
>  >> I might be able to speed up my bigintegers.4th
>  >
>  > I wonder if you could run a test for me: let p = 17**250 + 2704
>  > (this number happens to be prime) and time how long it takes for
>  > your implementation to do a Fermat test: calculate (3**p) mod p
>  > which should be equal to 3.
>  >
>  > My feeling is that if this takes less than a few seconds, your package
>  > is reasonably usable for public-key cryptography.
> 
> Out of curiosity, I tried this with the integer part of my forth-gmpfr
> package, which has a garbage collected bignum stack in ANS Forth, with
> bindings to the GNU Multiple Precision library:
> 
>    http://www.umich.edu/~williams/archive/forth/gmpfr/
> 
> I used pfe for the timings.  In the file names 3^p_mod_p_xxx.fs below,
> "xxx" indicates the number of trials.  The trials were run on a MacBook
> Pro 2.2 GHz Intel Core i7 (4 cores) under macOS Sierra 10.12.4.  The
> gmpfr package and GNU libraries used haven't been changed since January,
> 2012.
> 
> [haag:~/gmpfr] dnwills% /usr/bin/time -p pfe -q -y 3^p_mod_p_100.fs
> real         0.32
> user         0.31
> sys          0.00
> [haag:~/gmpfr] dnwills% /usr/bin/time -p pfe -q -y 3^p_mod_p_200.fs
> real         0.70
> user         0.69
> sys          0.00
> [haag:~/gmpfr] dnwills% /usr/bin/time -p pfe -q -y 3^p_mod_p_1000.fs
> real         2.95
> user         2.94
> sys          0.00
> 
> So the user time for one calculation is less than 3 milliseconds.  I
> don't know how much of that is bignum stack overhead, compared to the
> GNU library calls.
> 
> Here's the 1000-trial code:
> 
> 3^p_mod_p_1000.fs
> -----------------
> \  Title:   GMPFR Benchmark for (3**p) mod p with a large prime p
> \   File:   3^p_mod_p_1000.fs
> \  Author:  David N. Williams
> \    Date:  April 17, 2017
> \ License:  public domain
> 
> \ To run with pfe:
> \   /usr/bin/time -p pfe -q -y 3^p_mod_p_1000.fs
> 
> true constant MULTI-INTEGERS
> s" gmpfr.fs" INCLUDED
> 17 u>b 250 b^u 2704 bu+ bconstant p
> 
> : tries  ( n -- )
>    0 DO
>      3 u>b p p b-pow-mod  \ 3^p mod p
>      bdrop
>      \ b.
>    LOOP
> ;
> 
> 1000 tries
> bye
> -----------------
> 
> Here are some checks (long result broken into lines):
> 
> p b. 40947778423540104959067988292528857405972603447195632195037
> 8594747292053767136408255971273136413908600752651227962494772762
> 1804563995511385846512375859465262648854834054706258499178583491
> 6459459029262407818318245524277482110372262457010816382213629216
> 030118638993632313978231084140883786669390389605436763953 ok
> 3 u>b p p b-pow-mod b. 3 ok
> 
> I haven't tested whether the value of p above is correct, but at least
> it's big, odd, and produces 3 in the calculation.
> 
> -- David W.

That was fast. My hobby project started with trying to make arithmetic in ascii-strings and have developed to be several hundred times faster by time. But obviously there is much left to do.

The purpose with my ANS-Forth library is to have something to refer to when writing Forth code at OEIS, Euler, Rosetta etc that is easy to load.

I have loaded your gmpfr-0.9.0-file and will examine it. I knew there where that fast c-code, but I didn't know there was a stack based big integer for ANS Forth.

Lars-Erik Svahn
https://forthmath.blogspot.se
https://github.com/Lehs/ANS-Forth-libraries

[toc] | [prev] | [next] | [standalone]

#57526

lehs <skydda.barnen@gmail.com> writes:
> I have loaded your gmpfr-0.9.0-file and will examine it. I knew there
> where that fast c-code, 

GMP is extremely complicated and impressive and includes a lot of
assembly code, not just C.  It would be a huge amount of work to
replicate all the stuff that it does.  For example, it uses FFT-based
multiplication when the numbers involved are large enough.  It also
has a highly optimized version of modexp for use in crypto.

> but I didn't know there was a stack based big integer for ANS Forth.

That does sound helpful, that there's a wrapper ready to use.

[toc] | [prev] | [next] | [standalone]

#57535

Den tisdag 18 april 2017 kl. 04:21:58 UTC+2 skrev Paul Rubin:
> lehs <skydda.barnen@gmail.com> writes:
> > I have loaded your gmpfr-0.9.0-file and will examine it. I knew there
> > where that fast c-code, 
> 
> GMP is extremely complicated and impressive and includes a lot of
> assembly code, not just C.  It would be a huge amount of work to
> replicate all the stuff that it does.  For example, it uses FFT-based
> multiplication when the numbers involved are large enough.  It also
> has a highly optimized version of modexp for use in crypto.
> 
> > but I didn't know there was a stack based big integer for ANS Forth.
> 
> That does sound helpful, that there's a wrapper ready to use.

I'm not going to replicate it, but if I can understand how to make it work I could use it as it is. But even that seems very difficult.

[toc] | [prev] | [next] | [standalone]

#57569

lehs <skydda.barnen@gmail.com> writes:
> I'm not going to replicate it, but if I can understand how to make it
> work I could use it as it is. But even that seems very difficult.

It's not too bad from a C program, quite nice from C++, and from some
other languages that use it, you don't even notice it.  No idea about
Forth bindings.

[toc] | [prev] | [next] | [standalone]

#57558

On 4/17/17 9:21 PM, Paul Rubin wrote:
 > lehs <skydda.barnen@gmail.com> writes:
 >> I have loaded your gmpfr-0.9.0-file and will examine it. I knew there
 >> where that fast c-code,

Unfortunately I am no longer able to run it with the gforth installed on
my system.  Sometime in the next few weeks I'll try to update the GMP
and MPFR libraries and C-call interfaces.  Presumably the version that
Marcel built into iForth works fine.  I haven't been keeping up for
quite awhile now.

 > GMP is extremely complicated and impressive and includes a lot of
 > assembly code, not just C.  It would be a huge amount of work to
 > replicate all the stuff that it does.  For example, it uses FFT-based
 > multiplication when the numbers involved are large enough.  It also
 > has a highly optimized version of modexp for use in crypto.
 >
 >> but I didn't know there was a stack based big integer for ANS Forth.

Forth-gmpfr is an elaborate package, with garbage-collected stacks for
multiple precision integers, rationals, floats, and reliable floats.  My
attitude was that GMP and MPFR, as deep, deep implementations of
scientifically and mathematically significant problem domains, justify a
comprehensive treatment in interactive Forth.  Of course one doesn't
want to be more elaborate than necessary, and some simplification of the
package is surely possible.  But I did put quite a bit of effort into
keeping as much elaboration as possible under the hood, as far as the
user is concerned.

Interfacing with C libraries is itself a serious complication,
especially since we don't have an agreed upon, stable interface that
works with all the major Forths and is respected by updates to those
Forths (AFAIK).  Aside from the interface, one has to deal with updates
to the GMP and MPFR libraries.  Maybe mostly ignoring them is feasible.

 > That does sound helpful, that there's a wrapper ready to use.

It was at one point fairly ready to use, but it will take some work to
make that true now.

I certainly don't want to discourage the development of all-in-Forth
bignums.  Forth-gmpfr could be used for testing them.  I assume people
are aware of Len Zettel's version in the Forth Scientific Library:

   https://www.taygeta.com/fsl/library/big.fth

-- David W.

[toc] | [prev] | [next] | [standalone]

#57562

On Tuesday, April 18, 2017 at 3:11:53 AM UTC+2, David N. Williams wrote:
> On 4/17/17 3:19 AM, Paul Rubin wrote:
>  > lehs <skydda.barnen@gmail.com> writes:
>  >> I might be able to speed up my bigintegers.4th
>  >
>  > I wonder if you could run a test for me: let p = 17**250 + 2704
>  > (this number happens to be prime) and time how long it takes for
>  > your implementation to do a Fermat test: calculate (3**p) mod p
>  > which should be equal to 3.
>  >
>  > My feeling is that if this takes less than a few seconds, your package
>  > is reasonably usable for public-key cryptography.
> 
> Out of curiosity, I tried this with the integer part of my forth-gmpfr
> package, which has a garbage collected bignum stack in ANS Forth, with
> bindings to the GNU Multiple Precision library:
> 
>    http://www.umich.edu/~williams/archive/forth/gmpfr/
> 
> I used pfe for the timings.  In the file names 3^p_mod_p_xxx.fs below,
> "xxx" indicates the number of trials.  The trials were run on a MacBook
> Pro 2.2 GHz Intel Core i7 (4 cores) under macOS Sierra 10.12.4.  The
> gmpfr package and GNU libraries used haven't been changed since January,
> 2012.
> 
> [haag:~/gmpfr] dnwills% /usr/bin/time -p pfe -q -y 3^p_mod_p_100.fs
> real         0.32
> user         0.31
> sys          0.00
> [haag:~/gmpfr] dnwills% /usr/bin/time -p pfe -q -y 3^p_mod_p_200.fs
> real         0.70
> user         0.69
> sys          0.00
> [haag:~/gmpfr] dnwills% /usr/bin/time -p pfe -q -y 3^p_mod_p_1000.fs
> real         2.95
> user         2.94
> sys          0.00
> 
> So the user time for one calculation is less than 3 milliseconds.  I
> don't know how much of that is bignum stack overhead, compared to the
> GNU library calls.
> 
> Here's the 1000-trial code:
> 
> 3^p_mod_p_1000.fs
> -----------------
> \  Title:   GMPFR Benchmark for (3**p) mod p with a large prime p
> \   File:   3^p_mod_p_1000.fs
> \  Author:  David N. Williams
> \    Date:  April 17, 2017
> \ License:  public domain
> 
> \ To run with pfe:
> \   /usr/bin/time -p pfe -q -y 3^p_mod_p_1000.fs
> 
> true constant MULTI-INTEGERS
> s" gmpfr.fs" INCLUDED
> 17 u>b 250 b^u 2704 bu+ bconstant p
> 
> : tries  ( n -- )
>    0 DO
>      3 u>b p p b-pow-mod  \ 3^p mod p
>      bdrop
>      \ b.
>    LOOP
> ;
> 
> 1000 tries
> bye
> -----------------
> 
> Here are some checks (long result broken into lines):
> 
> p b. 40947778423540104959067988292528857405972603447195632195037
> 8594747292053767136408255971273136413908600752651227962494772762
> 1804563995511385846512375859465262648854834054706258499178583491
> 6459459029262407818318245524277482110372262457010816382213629216
> 030118638993632313978231084140883786669390389605436763953 ok
> 3 u>b p p b-pow-mod b. 3 ok
> 
> I haven't tested whether the value of p above is correct, but at least
> it's big, odd, and produces 3 in the calculation.
> 
> -- David W.

Out of curiosity, I tried this with one of the five 
bignum packages in iForth, the GINT:

NEEDS -factor

s" 3" s2 >giant
#17 #250 s1 Gm^n  s1 #2704 GS+ ( s1 = 17^250 + 2704 )
s1 .giant
\ 4094777842354010495906798829252885740597260344719563219503785947
\ 4729205376713640825597127313641390860075265122796249477276218045
\ 6399551138584651237585946526264885483405470625849917858349164594
\ 5902926240781831824552427748211037226245701081638221362921603011
\ 8638993632313978231084140883786669390389605436763953

s2 s1 s1 GG^MOD
s2 .giant ( should print 3)

: tries  ( n -- )
   CR DUP DEC. ." tries: "
   TIMER-RESET
   0 DO
     s" 3" s2 >giant
     s2 s1 s1 GG^MOD
   LOOP .ELAPSED ;

#1000 tries
1000 tries: 16.914 seconds elapsed. ok

It gives the same result as GMP for "p",
but its powermod takes 16ms / op, 5 times
slower than GMP.

(BTW, GMP does not use assembly unless you
 force it, as that would not work everywhere 
 without gas).

Unfortunately, the Forth bignum package doesn't
have a GG^MOD look-a-like, so I can't compare
that GMP/GINT (maybe lina has one?)

-marcel

[toc] | [prev] | [next] | [standalone]

#57660

In article <9b900b91-5158-4ebd-99f6-5af1888509f8@googlegroups.com>,
 <mhx@iae.nl> wrote:

>Unfortunately, the Forth bignum package doesn't
>have a GG^MOD look-a-like, so I can't compare
>that GMP/GINT (maybe lina has one?)

lina has " in the power modulo" or more clearly, one can set the
modulus and then one can do all sorts of arithmetic.
1,000,000,007 _m !
..... +m ... /m ... -m ... **m

This is only single precision though (and it takes only one screen).

Remember we had something like that on the transputer Forth?
I never came around to port that to lina.

>
>-marcel
>
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#57669

On Thursday, April 20, 2017 at 8:47:28 PM UTC+2, Albert van der Horst wrote:
> In article <9b900b91-5158-4ebd-99f6-5af1888509f8@googlegroups.com>,
>  <mhx@iae.nl> wrote:
>
> >Unfortunately, the Forth bignum package doesn't
> >have a GG^MOD look-a-like, so I can't compare
> >that GMP/GINT (maybe lina has one?)
>
[..]
> Remember we had something like that on the transputer Forth?
> I never came around to port that to lina.

I had indeed forgotten SSMod^ ( A B MM -- N ) in
mpqss\Jacobi.frt, but that word only processes
single cell numbers, so it is no use in the current
context.
 
-marcel

[toc] | [prev] | [next] | [standalone]

#57480

Den måndag 17 april 2017 kl. 08:09:17 UTC+2 skrev hughag...@gmail.com:
> On Sunday, April 16, 2017 at 10:42:48 PM UTC-7, hughag...@gmail.com wrote:
> > On Sunday, April 16, 2017 at 7:43:49 PM UTC-7, hughag...@gmail.com wrote:
> > > On Sunday, April 16, 2017 at 9:02:40 AM UTC-7, lehs wrote:
> > > > With this test my code ran 4 times faster.
> > > > 
> > > > \ : test1 0 do over$ over$ swap$ drop$ drop$ loop ; 
> > > > \ : test1 0 do sover sover sswap sdrop sdrop loop ;
> > > > 
> > > > The method with heaps and references is faster for SWAP.
> > > 
> > > I don't think this is true. None of those strings ever get put in the heap. ALLOCATE never gets called. No string is ever copied.
> > 
> > It is possible that you have an old version of STRING-STACK.4TH --- for a while, I had >$ making unique strings, which was not necessary most of the time (because most strings come from S" that is non-mutable) --- now I have >$ assume that the string is non-mutable and makes a derivative on the string-stack, and I have MUT>$ that is for mutable strings (such as <CSTR ... CSTR> strings) and these get converted into unique strings. I also have HEAP>$ that is for strings that are already on the heap (typically because they came from $> and got held in a data-structure for a while).
> 
> Actually, that wouldn't have much effect on the speed because >$ isn't inside of the loop. All you have inside of the loop are stack-juggling words, and these don't make unique strings (they don't call ALLOCATE and they don't copy the string); they just juggle references.
> 
> I think that you are just making up a bullshit story. There is no way that copying strings is 6 times (or 4 times) faster than copying a reference. STRING-STACK.4TH uses COW (copy-on-write) for the purpose of making it fast.

I don't blame you for the suspicion, but it was the result that I got. After had been repairing an error due to a wrap the code did paste-load on Win32Forth without numbers on the stack and the test was much faster (about a half second).

Maybe I will try to separate string-stack from the novice package and then eventually be able to understand how it works.

[toc] | [prev] | [next] | [standalone]

#57468

On Sunday, April 16, 2017 at 8:23:17 AM UTC-7, lehs wrote:
> Hugh, I tested your string stack against mine in Win32Forth 6.15.03, a simple test:
> 
> \ : test 0 do over$ over$ drop$ drop$ loop ; 
> \ : test 0 do sover sover sdrop sdrop loop ; 
> 
> and found that mine ran the test 6 times faster than your.
> 
> My string stack is a shitty hack without any kind of sophistication: no heaps, no error checks, no adress references just copying all strings when juggling...
> 
> I not assure how to interpret this, because I'm convinced you're a far better coder than me.

I don't know how to interpret this either. I don't believe that it is true.

empty$  ok
s" foo" >$  s" bar" >$  .s$ 
STRING STACK:
derivative: |bar|
derivative: |foo| ok
over$ over$  .s$ 
STRING STACK:
derivative: |bar|
derivative: |foo|
derivative: |bar|
derivative: |foo| ok
drop$ drop$  .s$ 
STRING STACK:
derivative: |bar|
derivative: |foo| ok

As you can see, this code works only with derivatives. It never calls ALLOCATE and it never copies a string.

You are telling me that copying entire strings, rather than copying a reference to the string, is 6 times faster? I don't believe that.

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.forth

csiph-web