On 21/05/2024 08:33, dxf wrote:

On 19/05/2024 1:41 am, Hans Bezemer wrote:

Well, this one is the longest I've published - and it took me some time to get there.

You can find it at: https://www.youtube.com/watch?v=gfE8arB3uWk

This could be one that gives rise to some discussion ;-)

At least I hope you're entertained!

Hans Bezemer

This SQRT from Wil Baden is claimed to be fast.
Modified here to return root and remainder.

: SQRT ( u -- rem root )
0 0 [ 4 CELLS ] LITERAL 0 DO
>R D2* D2* R> 2*
2DUP 2* U> IF
DUP >R 2* - 1- R> 1+
THEN
LOOP
ROT DROP ;

I would have found it earlier had I needed one. Never saw the value of translating algorithms myself esp. if someone had already done it. I'll
give it a look-over to see whether it needs a clean-up :)

There are several alternative definitions in this Dec 2022 discussion: https://groups.google.com/g/comp.lang.forth/c/Clci927n19Y/m/NEcAOh8ICgAJ

--
Gerry

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <664c4e61$1@news.ausics.net>, dxf <dxforth@gmail.com> wrote:

On 19/05/2024 1:41 am, Hans Bezemer wrote:

Well, this one is the longest I've published - and it took me some

time to get there.

You can find it at: https://www.youtube.com/watch?v=gfE8arB3uWk

This could be one that gives rise to some discussion ;-)

At least I hope you're entertained!

Hans Bezemer

This SQRT from Wil Baden is claimed to be fast.
Modified here to return root and remainder.

: SQRT ( u -- rem root )
0 0 [ 4 CELLS ] LITERAL 0 DO
>R D2* D2* R> 2*
2DUP 2* U> IF
DUP >R 2* - 1- R> 1+
THEN
LOOP
ROT DROP ;

I would have found it earlier had I needed one. Never saw the value of >translating algorithms myself esp. if someone had already done it. I'll
give it a look-over to see whether it needs a clean-up :)

In your case and if you use the Newton iteration it is mostly a log(n) process. The estimates go 1 --> 2 --> 4 --> 8 unless you are in the vicinity.

There is a speedup possible that I have used successfully in euler
problems. Seed the Newton iteration with the result of the previous
square root. That is the factor 10+ speedup you are waiting for.
If you are not calculating millions of roots, any speedup talk is moot.
This is my take.

HEX
: SQRT
DUP >R
000A RSHIFT 0400 MAX \ Shave 10 iterations in unfavourable cases.
BEGIN R@ OVER / OVER + 1 RSHIFT 2DUP > WHILE NIP REPEAT \ Newton.
DROP RDROP ;

And only core words.
The initial value (now 10/1024) can be remembered from previous time.

Mind the specification:
\ For N return FLOOR of the square root of n.

I hate "( u -- rem root )"
A number in the "vicinity of the square root", doesn't cut it for
mathematical problems.

And then 'u' . When was the last time you calculate a root between 8FFF,FFFF,FFFF,FFFF and FFFF,FFFF,FFFF,FFFF ?

Groetjes Albert
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat purring. - the Wise from Antrim -

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Do 23 May 24, 19:04 UTC+1, Hans Bezemer wrote:

If you think it's about the promotion of Forth, you're dead wrong. If anything, it's about the idea and the enigma of Forth. Whether you care
to share that fascination is entirely up to the viewer.

Quite right, I warn sharing what 100 million flies like to consume and
I'm sceptical about influencers. It's funny to read you, programmers
are a dying race. I like your insights and others here. Forth gives me
a grounding what's important. There exist much knowledge about
programming and languages but I've read the deeply frustration of
Wirth about ignoring his warnings of wasting ressources by lazy
programming, same observation made by Moore 60 years ago.

It's business driven subject and "Forth's the last resort of DIY" said
Moore :). Now you have a right to repair thing. A right to stop the
wastings in software maybe take another fifty years. Most younger
people are not interested at IT-jobs told me Heise-ticker today, I fear
not the dying of thinkful programming. Somebody sent me an
Chatgpt-comment to his script, an editor macro. Friendly blah an
commenting like this line of code do this and that line do that. He was
very impressed how intelligent the commentary was. Ok, that's a result
of working with 100 languages I suppose, you better take two or five
and really try to understand it and I didn't think at Python.

Hundred of planes cannot start because it's software is not actualized,
hello Chatgpt, "Even with slimmed-down software, it takes around a
year before the *** built on stockpiles are delivered." Brave new world.

--
Zong

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 23/05/2024 12:14, albert@spenarnc.xs4all.nl wrote:

And then 'u' . When was the last time you calculate a root between 8FFF,FFFF,FFFF,FFFF and FFFF,FFFF,FFFF,FFFF ?

You mean that you are happy that USQRT fails for half the integers
available to you. Anyway not everybody uses 64 bits.

--
Gerry

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <v3a3dq$1np8e$1@dont-email.me>,
Gerry Jackson <do-not-use@swldwa.uk> wrote:

On 23/05/2024 12:14, albert@spenarnc.xs4all.nl wrote:

And then 'u' . When was the last time you calculate a root between
8FFF,FFFF,FFFF,FFFF and FFFF,FFFF,FFFF,FFFF ?

You mean that you are happy that USQRT fails for half the integers
available to you. Anyway not everybody uses 64 bits.

If you claim that it works for unsigned numbers, then you have to
test for that. What happens to 0x8000 , a number where ABS doesn't
work? I'm happier ignoring those case, than writing tests for them.

--
Gerry

Groetjes Albert
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat purring. - the Wise from Antrim -

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 31/05/2024 10:23, albert@spenarnc.xs4all.nl wrote:

In article <v3a3dq$1np8e$1@dont-email.me>,
Gerry Jackson <do-not-use@swldwa.uk> wrote:

On 23/05/2024 12:14, albert@spenarnc.xs4all.nl wrote:

And then 'u' . When was the last time you calculate a root between
8FFF,FFFF,FFFF,FFFF and FFFF,FFFF,FFFF,FFFF ?

You mean that you are happy that USQRT fails for half the integers
available to you. Anyway not everybody uses 64 bits.

If you claim that it works for unsigned numbers, then you have to
test for that. What happens to 0x8000 , a number where ABS doesn't
work >

Given the definition I posted:

: usqrt ( u -- u1 )
dup 2 u< if exit then
dup >r 2 rshift recurse
2* ( -- u sm )
1+ dup ( -- u la la )
dup * ( -- u la la^2 )
r> u> if 1- then ( -- u1 )
;

and using the 32 bit equivalent of your 16 bit $8000 on my 32 bit system

$80000000 usqrt . 46340 ok

which according to my calculator is the correct answer and which
disproves the points you make.

I'm happier ignoring those case, than writing tests for them.
Groetjes Albert

I'm happier to not have to ignore any cases

--
Gerry

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

People don't come from FORTRAN/Alogol-like languages anymore.
They come from Python.

If you only use stacks in Forth, you have nothing to offer them
but limitations and confusion.

IOW, if you add classic heap-based data structures to Forth
and appropriate methods (GC not necessarily required), you
might be able to catch some of them with the size and speed of
of Forth.

Unfortunately, you will then be out in the wild, and you will
lose again, because you are not using accepted standards.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

LIT wrote:

If you only use stacks in Forth, you have nothing to offer them
but limitations and confusion.

Actually that's what programming in Forth is about; about
using stack for passing (and processing) values -- isn't it?

This is utter nonsense, unless you have a perverted lust for
stacks. A tool is there to solve problems. Who the heck has
stack problems?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

LIT wrote:

If you only use stacks in Forth, you have nothing to offer them
but limitations and confusion.

Actually that's what programming in Forth is about; about
using stack for passing (and processing) values -- isn't it?

I don't think so. Stacks are cute but they don't give the
language unique capabilities that can't be replicated or
approximated in other languages.

In my opinion Forth is unique because it allows to writes one's
own fully customized toolboxes, down to the parsing and
compilation of the application language. There are still many
areas where this matters.

-marcel

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

dxf wrote:

[..]

This SQRT from Wil Baden is claimed to be fast.
Modified here to return root and remainder.

Unmodified to compare with NR without smart first choice.

ANEW -root

\ Newton-Raphson
: root ( n -- root | 0 )
DUP 0<= IF DROP 0 EXIT ENDIF ( root of negative number )
DUP >R ( -- xj ) ( R: -- n )
BEGIN DUP R@ OVER / + 2/ \ xj+1 = 0.5*(n/xj+xj)
( xj xj+1 ) 2DUP >
WHILE NIP ( xj+1 )
REPEAT DROP ( xj ) -R ;

\ dxf Tue, 21 May 2024 09:33
: root2 ( u -- root )
0 0 [ 4 CELLS ] LITERAL 0 DO
>R D2* D2* R> 2*
2DUP 2* U> IF
DUP >R 2* - 1- R> 1+
THEN
LOOP
NIP NIP ;

\ tested upto 1,000,000,000 : 23ns/root
: roottest ( -- )
TICKS-RESET #1000000000 0 ?DO I root DROP LOOP
TICKS? ( TICKS>US ) #1000000 UM/MOD NIP
. ." ticks/root." ;

\ tested upto 1,000,000,000 : 44ns/root
: roottest2 ( -- )
TICKS-RESET #1000000000 0 ?DO I root2 DROP LOOP
TICKS? ( TICKS>US ) #1000000 UM/MOD NIP
. ." ticks/root." ;

FORTH> 1 root2 . 1 ok
FORTH> 0 root2 . 0 ok
FORTH> -1 root2 . 4294967295 ok
FORTH> -1 root2 h. $FFFFFFFF ok

\ roottest : 109,445 ticks/root.
\ roottest2 : 184,308 ticks/root. ok

Quite a difference.

-marcel

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Sorry, that should've been (AMD 5800X):

\ roottest : 109 ticks/root.
\ roottest2 : 184 ticks/root.

-marcel

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

dxf wrote:

On 4/06/2024 8:30 am, mhx wrote:

Sorry, that should've been (AMD 5800X):

\ roottest  : 109 ticks/root.
\ roottest2 : 184 ticks/root.

Individual circumstances can be a factor e.g. second routine is
unsigned. For my use (16-bit DTC) I found Gerry's routine to be
shorter and faster than Baden's.

The first one uses Newton-Raphson (quadratical convergence)
but pays for that with the '/' instruction. The algorithm of
the second routine is unclear but uses (in principle) only
very fast shift instructions. My guess would be that Baden's
original simply uses many more steps.

I think AMD improved integer division some time ago.

-marcel

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <decd1016d9d3097e2fc059c853395b81@www.novabbs.com>,
mhx <mhx@iae.nl> wrote:

dxf wrote:

On 4/06/2024 8:30 am, mhx wrote:

Sorry, that should've been (AMD 5800X):

\ roottest  : 109 ticks/root.
\ roottest2 : 184 ticks/root.

Individual circumstances can be a factor e.g. second routine is
unsigned. For my use (16-bit DTC) I found Gerry's routine to be
shorter and faster than Baden's.

The first one uses Newton-Raphson (quadratical convergence)
but pays for that with the '/' instruction. The algorithm of
the second routine is unclear but uses (in principle) only
very fast shift instructions. My guess would be that Baden's
original simply uses many more steps.

Newton Raphson's quadratic convergence doesn't help if your
starting point is far away.
Both methods are O(CELL) .
For me it is a wash, not an order of magnitude.

I think AMD improved integer division some time ago.

If your integer division is not fast (early 286 386) the
shift method is preferable, probably.

-marcel

Groetjes Albert
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat purring. - the Wise from Antrim -

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 18 Nov 2024 at 18:28:20 CET, "Hans Bezemer" <the.beez.speaks@gmail.com> wrote:

This time, we delve into a forgotten way to handle fixed point
arithmetic. Which IMHO deserves to be dusted off now we entered the
64-bit era!

https://www.youtube.com/watch?v=VwPForQL10Y

Hans Bezemer

Nice presentation.

Stephen
--
Stephen Pelc, stephen@vfxforth.com
MicroProcessor Engineering, Ltd. - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 (0)78 0390 3612, +34 649 662 974
http://www.mpeforth.com
MPE website
http://www.vfxforth.com/downloads/VfxCommunity/
downloads

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <nnd$0729bd17$4f184982@a8d623d456fa3140>,
Hans Bezemer <the.beez.speaks@gmail.com> wrote:

This time, we delve into a forgotten way to handle fixed point
arithmetic. Which IMHO deserves to be dusted off now we entered the
64-bit era!

https://www.youtube.com/watch?v=VwPForQL10Y

A one screen fixed point:
----------------------
( *s /s fix-scale -fixedpoint- ) \ AvdH C3nov06
WANT ALIAS
8 CELLS 4 - CONSTANT fix-scale \ n represents n.2^-scale.
1 fix-scale LSHIFT CONSTANT 1/1
1 fix-scale 1- LSHIFT CONSTANT 1/2
\ As */ * / but scaled.
: */s >R UM* R> UM/MOD NIP ;
: *s 1/1 */s ; : /s 1/1 SWAP */s ;
\ Most other operators remain the same:
'+ ALIAS +s '- ALIAS -s '*/ ALIAS */s
\ For a RATIO (n/d) return an equivalent scaled NUMBER.
'/s ALIAS rat>s \ By accident.
\ Print a scaled double number
: .mantissa 0 DO BASE @ 1/1 */MOD &0 + EMIT LOOP DROP SPACE ;
: _D.s 1/1 UM/MOD 0 <# #S #> TYPE &. EMIT 20 .mantissa ;
: U.s 0 _D.s ;
--------------------

For ISO replace '+ by ' + or ['] + .
(I can't remember which is which.)

ALIAS gives a new name for an old thing.
In a pinch do
: */s */ ;

WANT signifies that you want ALIAS if it isn't loaded already.

Hans Bezemer

--
Temu exploits Christians: (Disclaimer, only 10 apostles)
Last Supper Acrylic Suncatcher - 15Cm Round Stained Glass- Style Wall
Art For Home, Office And Garden Decor - Perfect For Windows, Bars,
And Gifts For Friends Family And Colleagues.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)