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

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

Compiled Forth

Started bylehs <skydda.barnen@gmail.com>
First post2015-04-04 12:02 -0700
Last post2015-04-10 04:50 -0700
Articles 12 on this page of 92 — 12 participants

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

Contents

  Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-04 12:02 -0700
    Re: Compiled Forth "Elizabeth D. Rather" <erather@forth.com> - 2015-04-04 14:43 -1000
      Re: Compiled Forth hughaguilar96@gmail.com - 2015-04-04 18:16 -0700
        Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-05 10:58 -0700
      Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-05 10:52 -0700
        Re: Compiled Forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-04-06 15:35 +0000
          Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-06 08:51 -0700
            Re: Compiled Forth mhx@iae.nl - 2015-04-06 15:32 -0700
              Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-06 16:28 -0700
                Re: Compiled Forth mhx@iae.nl - 2015-04-08 13:58 -0700
                  Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-08 14:41 -0700
                    Re: Compiled Forth "Elizabeth D. Rather" <erather@forth.com> - 2015-04-08 14:01 -1000
                      Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-09 00:06 -0700
                      Re: Compiled Forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-10 16:48 +0000
                        Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 10:23 -0700
                          Re: Compiled Forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-10 18:04 +0000
                  Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-09 10:31 -0700
                    Re: Compiled Forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-09 17:57 +0000
                      Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-09 11:06 -0700
                      Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-22 09:17 -0700
          Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-06 09:01 -0700
    Re: Compiled Forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-04-05 09:32 +0000
      Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-05 11:02 -0700
        Re: Compiled Forth "HAA" <someone@microsoft.com> - 2015-04-06 18:35 +1000
    Re: Compiled Forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-05 09:52 +0000
      Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-05 11:20 -0700
      Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-05 11:57 -0700
        Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-05 12:05 -0700
          Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-05 12:47 -0700
            Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-05 13:36 -0700
              Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-05 13:57 -0700
                Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-05 14:37 -0700
                  Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-05 15:10 -0700
                    Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-05 15:23 -0700
        Re: Compiled Forth Ron Aaron <rambamist@gmail.com> - 2015-04-06 08:52 +0300
          Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-05 23:09 -0700
            Re: Compiled Forth Ron Aaron <rambamist@gmail.com> - 2015-04-06 10:12 +0300
            Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-06 00:15 -0700
              Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-06 01:05 -0700
                Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-06 01:27 -0700
              Re: Compiled Forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-04-06 12:20 +0000
            Re: Compiled Forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-04-06 12:10 +0000
              Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-06 11:45 -0700
                Re: Compiled Forth Melzzzzz <mel@zzzzz.com> - 2015-04-06 21:16 +0200
                  Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-06 12:55 -0700
          Re: Compiled Forth Jan Coombs <Jan-54 <jenfhaomndgfwutc@murmic.plus.com>> - 2015-04-06 09:01 +0100
            Re: Compiled Forth Ron Aaron <rambamist@gmail.com> - 2015-04-06 11:27 +0300
        Re: Compiled Forth Jan Coombs <Jan-54 <jenfhaomndgfwutc@murmic.plus.com>> - 2015-04-06 08:06 +0100
        Re: Compiled Forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-06 14:15 +0000
    Re: Compiled Forth stephen@mpeforth.com (Stephen Pelc) - 2015-04-06 11:32 +0000
    Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-06 08:01 -0700
      Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-06 12:04 -0700
        Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-06 12:58 -0700
          Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-06 13:29 -0700
            Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-06 16:44 -0700
              Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-06 19:59 -0700
                Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-07 01:31 -0700
                  Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-07 01:36 -0700
                  Re: Compiled Forth Jan Coombs <Jan-54 <jenfhaomndgfwutc@murmic.plus.com>> - 2015-04-07 12:00 +0100
                    Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-07 04:25 -0700
                      Proposal for ALLOCATEd bignum's Re: Compiled Forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-07 12:41 +0000
                      Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-08 21:40 -0700
                        Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-09 00:18 -0700
                  Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-09 23:43 -0700
                    Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 04:07 -0700
                      Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 04:37 -0700
                    Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 04:45 -0700
                      Re: Compiled Forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-10 12:02 +0000
                        Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 07:21 -0700
                          Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 07:53 -0700
                            Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 09:43 -0700
                            Re: Compiled Forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-10 16:43 +0000
                              Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 11:03 -0700
                                Re: Compiled Forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-10 18:26 +0000
                                Re: Compiled Forth mhx@iae.nl - 2015-04-10 11:27 -0700
                                  Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 11:36 -0700
                                    Re: Compiled Forth mhx@iae.nl - 2015-04-10 11:56 -0700
                                    Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-10 12:20 -0700
                                      Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 13:00 -0700
                                        Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-10 13:14 -0700
                                          Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 13:29 -0700
                                            Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-10 16:08 -0700
                                              Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 23:08 -0700
                                        Re: Compiled Forth mhx@iae.nl - 2015-04-11 01:59 -0700
                                          Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-11 02:20 -0700
                                          Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-11 02:44 -0700
                                            Re: Compiled Forth mhx@iae.nl - 2015-04-11 11:21 -0700
                                        Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-11 11:43 -0700
                                          Re: Compiled Forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-11 19:44 +0000
                                            Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-11 12:51 -0700
                                              Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-11 15:26 -0700
                    Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 04:50 -0700

Page 5 of 5 — ← Prev page 1 2 3 4 [5]

#38107

Fromlehs <skydda.barnen@gmail.com>
Date2015-04-10 13:29 -0700
Message-ID<bd6612c2-314e-4101-9c6b-fa02e9999b68@googlegroups.com>
In reply to#38104
Den fredag 10 april 2015 kl. 22:14:30 UTC+2 skrev Paul Rubin:
> lehs <skydda.barnen@gmail.com> writes:
> > I'm also sure that a modern multicore 64-bit system is more than twice
> > times faster than my 32-bit single core Celeron.
> 
> I'd expect Marcel tested on a single core, so multicore isn't an issue.
> What is the model number of your Celeron?  You can look at
> cpubenchmark.net for general speed comparison, though for specific
> operations like arithmetic the benchmark numbers may not mean much.
> 
> 64 bits does make a big difference.  In 32-bit mode on a 2.67GHz Xeon
> X5650 (older box), I get around 3 msec for that modexp.  On an ARM v7
> (don't know clock speed, maybe 1 ghz?) I get around 16 msec.
> 
> You can visit instantcloud.io and use a dedicated quad core ARM server
> at no charge for 30 minutes if that's of any interest--that's what I
> used for that test.  They rent them for 10 euro a month so the 30 minute
> thing is a tryout.
> 
> > What really interests me is if my approach with block moving stack
> > manipulation is comparable with professional solutions. Since my "bad"
> > algorithms probably are responsible for the most slowness - the system
> > might not be so bad.
> 
> Hard to say, there are a lot of variables.  Maybe some profiling is
> possible.  Can you get the program to work with gforth?

I loaded gforth-0.7.0.exe on http://www.complang.tuwien.ac.at/forth/gforth/ and it runs with the most actual version for case insensitivity on 
https://www.dropbox.com/s/nwzpluiehlhba4t/bigforth%20ANS%20Forth%20ins.txt?dl=0

Thanks for the links!

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

#38109

FromPaul Rubin <no.email@nospam.invalid>
Date2015-04-10 16:08 -0700
Message-ID<87vbh3bmz7.fsf@jester.gateway.sonic.net>
In reply to#38107
lehs <skydda.barnen@gmail.com> writes:
> I loaded gforth-0.7.0.exe on
> http://www.complang.tuwien.ac.at/forth/gforth/ and it runs with the
> most actual version for case insensitivity on
> https://www.dropbox.com/s/nwzpluiehlhba4t/bigforth%20ANS%20Forth%20ins.txt?dl=0

I replaced the commented out second-to-last line with

: test CL B 10 B 29 B** B 5342347 B+ BNEXT_PRIME B 10 B 31 
    B** B 2232788 B+ BNEXT_PRIME .B B* BHART .B ;

Running "test" then gives:

    :1: Invalid memory address
    test>>><<<
    Backtrace:
    $B72024CC cmove 
    $B72026D8 XPUSH 
    $B7202818 V>X 
    $B7202C10 VSWAP 
    $B7202D60 VR< 
    $B7202F50 VR= 
    $1 
    $9 
    $B7203144 V>BYTE 
    $B7206514 
    $B7206914 
    $B7203378 V>B 
    $B7206400 B 

This is on 32 bit linux.  I got a similar error with 64-bit linux but
thought that the word size might be the problem so I tried a 32-bit
system.

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

#38113

Fromlehs <skydda.barnen@gmail.com>
Date2015-04-10 23:08 -0700
Message-ID<e6cc83fb-1878-4d34-8d75-abe6dcc3a5a4@googlegroups.com>
In reply to#38109
Den lördag 11 april 2015 kl. 01:08:30 UTC+2 skrev Paul Rubin:
> lehs <skydda.barnen@gmail.com> writes:
> > I loaded gforth-0.7.0.exe on
> > http://www.complang.tuwien.ac.at/forth/gforth/ and it runs with the
> > most actual version for case insensitivity on
> > https://www.dropbox.com/s/nwzpluiehlhba4t/bigforth%20ANS%20Forth%20ins.txt?dl=0
> 
> I replaced the commented out second-to-last line with
> 
> : test CL B 10 B 29 B** B 5342347 B+ BNEXT_PRIME B 10 B 31 
>     B** B 2232788 B+ BNEXT_PRIME .B B* BHART .B ;
> 
> Running "test" then gives:
> 
>     :1: Invalid memory address
>     test>>><<<
>     Backtrace:
>     $B72024CC cmove 
>     $B72026D8 XPUSH 
>     $B7202818 V>X 
>     $B7202C10 VSWAP 
>     $B7202D60 VR< 
>     $B7202F50 VR= 
>     $1 
>     $9 
>     $B7203144 V>BYTE 
>     $B7206514 
>     $B7206914 
>     $B7203378 V>B 
>     $B7206400 B 
> 
> This is on 32 bit linux.  I got a similar error with 64-bit linux but
> thought that the word size might be the problem so I tried a 32-bit
> system.

I should have pointed it out better, but B can't be used in definitions.

Some instructions: https://www.dropbox.com/s/yrhthx1twbrsggv/Read%20me%20ins.txt?dl=0

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

#38119

Frommhx@iae.nl
Date2015-04-11 01:59 -0700
Message-ID<44c9563a-d361-44f1-971f-89b37d1ebd35@googlegroups.com>
In reply to#38102
On Friday, April 10, 2015 at 10:00:41 PM UTC+2, lehs wrote:
> Den fredag 10 april 2015 kl. 21:20:32 UTC+2 skrev Paul Rubin:
> > lehs <skydda.barnen@gmail.com> writes:
> > > It looks like all the calculations are correct.
> > > What processor did you use? How much faster is it than my Celeron 900
> > > 2.20 GHz?
> > 
> > I expect Marcel is using native-code compilation and maybe better
> > algorithms.  That will make a much bigger difference than more cpu
> > speed.  His cpu is maybe 2x faster at best (higher clock rate plus some
> > architectural tweaks).  OpenSSL on a 3.4 ghz i7-3770 takes about 0.5
> > msec for a 1024 bit modexp and that's probably close to optimum, short
> > of using a GPU etc.

It appears to be four times faster from the below
results, where I use the proposed code at fetched
from dropbox.
CASE/OF etc. is commented out as the  drp  in it
seems wrong. The four times is assuming SP-Forth's
compiler is as good as iForth's.
 
> I'm sure Marscel's is using better algorithms than mine.
> For example am I using "schoolbook" version of multiplication
> and since B**MOD mostly is built up by B* and BMOD, and BMOD
> mostly is built up by B* - so a faster B* could make some difference.
> 
> I'm also sure that a modern multicore 64-bit system is more than
> twice times faster than my 32-bit single core Celeron.

Nope.

> What really interests me is if my approach with block
> moving stack manipulation is comparable with professional
> solutions. Since my "bad" algorithms probably are responsible
> for the most slowness - the system might not be so bad.

It is clearly a very bad idea. Here is your code on iForth64:

FORTH> in
Redefining CELL-
Redefining RANDOM
Redefining NEXT
Redefining BSWAP
Redefining BRIGHT
Redefining B.
Redefining .X

0.701 seconds elapsed.
135891523556614188004809231968808929582425403055919116822282895312458319926165435401530460756504974233413880678347623424174558730165
100762234125930805396256961043240764866117547156296134403689228799197376998122532074740059603789432043783522667945458446845133628917
86202126506784931492440650088987888029494246  ok

The ratio between 701 ms and 16 ms says something about
your algorithms, the ratio between 16 ms and 3 ms
something about iForth, unless still better algorithms
exist :-)

-marcel

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

#38120

Fromlehs <skydda.barnen@gmail.com>
Date2015-04-11 02:20 -0700
Message-ID<2d81774e-eccd-484f-9ea8-ab6c37e71d70@googlegroups.com>
In reply to#38119
Den lördag 11 april 2015 kl. 10:59:24 UTC+2 skrev m...@iae.nl:
> On Friday, April 10, 2015 at 10:00:41 PM UTC+2, lehs wrote:
> > Den fredag 10 april 2015 kl. 21:20:32 UTC+2 skrev Paul Rubin:
> > > lehs <skydda.barnen@gmail.com> writes:
> > > > It looks like all the calculations are correct.
> > > > What processor did you use? How much faster is it than my Celeron 900
> > > > 2.20 GHz?
> > > 
> > > I expect Marcel is using native-code compilation and maybe better
> > > algorithms.  That will make a much bigger difference than more cpu
> > > speed.  His cpu is maybe 2x faster at best (higher clock rate plus some
> > > architectural tweaks).  OpenSSL on a 3.4 ghz i7-3770 takes about 0.5
> > > msec for a 1024 bit modexp and that's probably close to optimum, short
> > > of using a GPU etc.
> 
> It appears to be four times faster from the below
> results, where I use the proposed code at fetched
> from dropbox.
> CASE/OF etc. is commented out as the  drp  in it
> seems wrong. The four times is assuming SP-Forth's
> compiler is as good as iForth's.
>  
> > I'm sure Marscel's is using better algorithms than mine.
> > For example am I using "schoolbook" version of multiplication
> > and since B**MOD mostly is built up by B* and BMOD, and BMOD
> > mostly is built up by B* - so a faster B* could make some difference.
> > 
> > I'm also sure that a modern multicore 64-bit system is more than
> > twice times faster than my 32-bit single core Celeron.
> 
> Nope.
> 
> > What really interests me is if my approach with block
> > moving stack manipulation is comparable with professional
> > solutions. Since my "bad" algorithms probably are responsible
> > for the most slowness - the system might not be so bad.
> 
> It is clearly a very bad idea. Here is your code on iForth64:
> 
> FORTH> in
> Redefining CELL-
> Redefining RANDOM
> Redefining NEXT
> Redefining BSWAP
> Redefining BRIGHT
> Redefining B.
> Redefining .X
> 
> 0.701 seconds elapsed.
> 135891523556614188004809231968808929582425403055919116822282895312458319926165435401530460756504974233413880678347623424174558730165
> 100762234125930805396256961043240764866117547156296134403689228799197376998122532074740059603789432043783522667945458446845133628917
> 86202126506784931492440650088987888029494246  ok
> 
> The ratio between 701 ms and 16 ms says something about
> your algorithms, the ratio between 16 ms and 3 ms
> something about iForth, unless still better algorithms
> exist :-)
> 
> -marcel

First of all, thank you very much for the feedback!

The drp in the CASE-structure come from using replace in the editor when I was lazy in trying to make the code case insensible. I have corrected that, but can't understand how it could run in my tests...

I don't understand:

> FORTH> in
> Redefining CELL-
> Redefining RANDOM
> Redefining NEXT
> Redefining BSWAP
> Redefining BRIGHT
> Redefining B.
> Redefining .X

Did your system used my CELL-, RANDOM, ... and then run that much slower?

I know that my algorithms could be replaced (which I e´will try to do later) but what I mean with "my system" is the way I handle bigint and the stack of bigint.

If I could understand what code you have measured I could consider the idea of "my system" to see if it is worth while working further with the algorithms or if I have to reorganize before.

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

#38121

Fromlehs <skydda.barnen@gmail.com>
Date2015-04-11 02:44 -0700
Message-ID<35a06aad-b8f8-45e7-8b02-3ddb463c2719@googlegroups.com>
In reply to#38119
Den lördag 11 april 2015 kl. 10:59:24 UTC+2 skrev m...@iae.nl:
> On Friday, April 10, 2015 at 10:00:41 PM UTC+2, lehs wrote:
> > Den fredag 10 april 2015 kl. 21:20:32 UTC+2 skrev Paul Rubin:
> > > lehs <skydda.barnen@gmail.com> writes:
> > > > It looks like all the calculations are correct.
> > > > What processor did you use? How much faster is it than my Celeron 900
> > > > 2.20 GHz?
> > > 
> > > I expect Marcel is using native-code compilation and maybe better
> > > algorithms.  That will make a much bigger difference than more cpu
> > > speed.  His cpu is maybe 2x faster at best (higher clock rate plus some
> > > architectural tweaks).  OpenSSL on a 3.4 ghz i7-3770 takes about 0.5
> > > msec for a 1024 bit modexp and that's probably close to optimum, short
> > > of using a GPU etc.
> 
> It appears to be four times faster from the below
> results, where I use the proposed code at fetched
> from dropbox.
> CASE/OF etc. is commented out as the  drp  in it
> seems wrong. The four times is assuming SP-Forth's
> compiler is as good as iForth's.
>  
> > I'm sure Marscel's is using better algorithms than mine.
> > For example am I using "schoolbook" version of multiplication
> > and since B**MOD mostly is built up by B* and BMOD, and BMOD
> > mostly is built up by B* - so a faster B* could make some difference.
> > 
> > I'm also sure that a modern multicore 64-bit system is more than
> > twice times faster than my 32-bit single core Celeron.
> 
> Nope.
> 
> > What really interests me is if my approach with block
> > moving stack manipulation is comparable with professional
> > solutions. Since my "bad" algorithms probably are responsible
> > for the most slowness - the system might not be so bad.
> 
> It is clearly a very bad idea. Here is your code on iForth64:
> 
> FORTH> in
> Redefining CELL-
> Redefining RANDOM
> Redefining NEXT
> Redefining BSWAP
> Redefining BRIGHT
> Redefining B.
> Redefining .X
> 
> 0.701 seconds elapsed.
> 135891523556614188004809231968808929582425403055919116822282895312458319926165435401530460756504974233413880678347623424174558730165
> 100762234125930805396256961043240764866117547156296134403689228799197376998122532074740059603789432043783522667945458446845133628917
> 86202126506784931492440650088987888029494246  ok
> 
> The ratio between 701 ms and 16 ms says something about
> your algorithms, the ratio between 16 ms and 3 ms
> something about iForth, unless still better algorithms
> exist :-)
> 
> -marcel

OK! Now I understand! You loaded SP-Forth (Windows? Linux?) and then my code and made it work (32/64?).

And then my code was about 50 times slower than your package. That is much, but I still don't know what comes from bad algorithms and what comes from the idea of copying code when manipulating the stack without knowing if the code is going to be changed.

I will never make coded algorithms comparable with professional programmers. So a factor of 5 times has to be corrected. Then 10 times faster seems to be possible to reach by optimizing the temporary stack manipulation words, by using a faster multiplication (doubled number of digits causes 4 times slower execution with my temporary B*) and pull my self together and write adequate big shifts.

I I'll manage to near the 5-times-slower-than-yours I'll consider the stack coping method as adequate.

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

#38129

Frommhx@iae.nl
Date2015-04-11 11:21 -0700
Message-ID<4cb05c92-6d34-4406-9553-eb77a1529867@googlegroups.com>
In reply to#38121
On Saturday, April 11, 2015 at 11:44:00 AM UTC+2, lehs wrote:
> OK! Now I understand! You loaded SP-Forth (Windows? Linux?)
> and then my code and made it work (32/64?).

No, I downloaded your last(?) dropbox file, commented out the
CASE/OF code and then it ran on iForth64 (a 64-bit Windows /
Linux / OSX Forth).

However, I only tested the B**MOD code. The other words seem
to crash a lot.

I have not enough interest in SP-Forth to try it out (again).
I remember it is a very good compiler.
 
> And then my code was about 50 times slower than your package.
> That is much, but I still don't know what comes from bad
> algorithms and what comes from the idea of copying code
> when manipulating the stack without knowing if the code
> is going to be changed.
 
I compared against the GINT package, which also uses a stack
for its giant ints. So I can say that better algorithms are
possible, or that you have a really bad implementation
somewhere.

> I will never make coded algorithms comparable with
> professional programmers. So a factor of 5 times
> has to be corrected. Then 10 times faster seems
> to be possible to reach by optimizing the temporary
> stack manipulation words, by using a faster
> multiplication (doubled number of digits causes
> 4 times slower execution with my temporary B*)
> and pull my self together and write adequate 
> big shifts.

Yes.
 
> I I'll manage to near the 5-times-slower-than-yours 
> I'll consider the stack coping method as adequate.

Of course.

-marcel

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

#38131

FromPaul Rubin <no.email@nospam.invalid>
Date2015-04-11 11:43 -0700
Message-ID<87lhhya4lc.fsf@jester.gateway.sonic.net>
In reply to#38102
lehs <skydda.barnen@gmail.com> writes:
> I'm sure Marscel's is using better algorithms than mine. For example
> am I using "schoolbook" version of multiplication

General wisdom is that fancier multiplication methods (Karatsuba,
Toom-Cook, etc.) don't become faster than schoolbook methods until
you're in the 1000's of digits, not 100's.  Of course it will depend on
the implementation.  You might try Karatsuba first, since it's easy to
understand and implement.

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

#38132

Fromalbert@spenarnc.xs4all.nl (Albert van der Horst)
Date2015-04-11 19:44 +0000
Message-ID<552979a5$0$21295$e4fe514c@dreader37.news.xs4all.nl>
In reply to#38131
In article <87lhhya4lc.fsf@jester.gateway.sonic.net>,
Paul Rubin  <no.email@nospam.invalid> wrote:
>lehs <skydda.barnen@gmail.com> writes:
>> I'm sure Marscel's is using better algorithms than mine. For example
>> am I using "schoolbook" version of multiplication
>
>General wisdom is that fancier multiplication methods (Karatsuba,
>Toom-Cook, etc.) don't become faster than schoolbook methods until
>you're in the 1000's of digits, not 100's.  Of course it will depend on
>the implementation.  You might try Karatsuba first, since it's easy to
>understand and implement.

I remember having implemented Toom-Cook once (1990) in C from Knuth,
and was very disappointed with the performance.
(VAX and Unix).

The pdf that lehs mentioned has a lot of data about speed, up to
millions of bits. I picked up an important notion. If you have to
do a lot of MOD calculation with the same divider, it pays of to
calculate the inverse. This applies of course power modulo
calculations that occur very often in research and also in e.g. RSA.


Groetjes Albert
-- 
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]

#38133

FromPaul Rubin <no.email@nospam.invalid>
Date2015-04-11 12:51 -0700
Message-ID<87h9sma1fw.fsf@jester.gateway.sonic.net>
In reply to#38132
albert@spenarnc.xs4all.nl (Albert van der Horst) writes:
> The pdf that lehs mentioned has a lot of data about speed, up to
> millions of bits. I picked up an important notion. If you have to
> do a lot of MOD calculation with the same divider, it pays of to
> calculate the inverse. This applies of course power modulo
> calculations that occur very often in research and also in e.g. RSA.

For B**MOD you want the Montgomery representation of the number, which
converts all the MOD operations to mod by a power of 2.  

https://en.wikipedia.org/wiki/Montgomery_modular_multiplication

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

#38137

Fromlehs <skydda.barnen@gmail.com>
Date2015-04-11 15:26 -0700
Message-ID<f9b50607-77ea-4e5e-9efe-0cc683748a2b@googlegroups.com>
In reply to#38133
Both methods looks interesting: count the inverse and use that trick of Montgomery. 

It seems that my algorithms even are more primitive than I thought.

However, I'm in the mode to make an other revision of my bigint-system. I didn't realize that ALLOCATE and FREE was that rapid (though RESIZE is slow), so it looks interesting to use a separate reference stack pointing at allocated buffers. But there will be no GC, the usual stack operations will handle it all:

- the switching words BSWAP, BROT, B-ROT will just switch references.
- the dropping words BDROP and BNIP will FREE the buffer corresponding to the dropped bigint.
- the copying words DUP, OVER, TUCK will ALLOCATE buffers and copy.

I will try it and compare with my current system. And work on the algorithms. And while working on the new idea I will consider what I learned about standard and portability.

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

#38080

Fromlehs <skydda.barnen@gmail.com>
Date2015-04-10 04:50 -0700
Message-ID<b84e7e8c-7f5b-4a64-b9d5-b247cccf23b0@googlegroups.com>
In reply to#38074
Den fredag 10 april 2015 kl. 08:43:52 UTC+2 skrev Paul Rubin:
> lehs <skydda.barnen@gmail.com> writes:
> > B 16357961957638769631974563151376597136591375613975613 B**MOD
> > instantly (with my system in 4/100 second) gives 
> > 6639276191969705355236646500004312964523609080804143
> 
> I'd be interested to know the speed of B**MOD when all 3 args are 308
> decimal digits (1024 bits), if you feel like giving that a try.

With these numbers

26359783991551070871965201979080333254038743646746158379582192038055842791146833506745978666309678710238746262325665407448047112858614221184120023774728850927701745782077979943165434355776993447809155163506304287949484786229043007193369097865681445643720004387345872800008950502312482268122160708155160328564

39327375191467048647521018841730348998598651522372708158670691892420060531890655533991461398550696324722351925617448324344083141484661951392820800479947685042791549748743564268081958080246132723174581232969062661990556972176861792341905425252382562697686127413259201904144867482279552760624394742040590855602

16306675630939784626502807161425612212340131109932460322238576590610976549235432503764166590338557086651302692446204937053886057954003032814801648230668894753863150108029570966337696939560565101312815273803547555619029325583815565767168841836143511237512006023630352590540140638620838094344583215840893265550

B**MOD executed in 2480 ms with optimized SP-Forth on my laptop Celeron 900 2.20 GHz.

[toc] | [prev] | [standalone]

Page 5 of 5 — ← Prev page 1 2 3 4 [5]

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

csiph-web