"Back & Forth" is back!

[Hans Bezemer]

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

You can find it at:

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

At least I hope you're entertained!

Hans Bezemer

[dxf]

Well, this one is the longest I've published - and it took me some time to get there.
You can find it at: http://youtu.be/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 :)

[Gerry Jackson]

Post by dxf

Well, this one is the longest I've published - and it took me some time to get there.
You can find it at: http://youtu.be/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

[Hans Bezemer]

Post by dxf

Well, this one is the longest I've published - and it took me some time to get there.
You can find it at: http://youtu.be/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 :)

Sometimes it's not about the destination, but about the voyage. If I
wanted to do an item on "the fastest integer square root" algorithm, I
wouldn't have called it "Why is Forth so hard", but "The fastest integer
square root algorithm".

Hans Bezemer

[dxf]

...
Sometimes it's not about the destination, but about the voyage. If I wanted to do an item on "the fastest integer square root" algorithm, I wouldn't have called it "Why is Forth so hard", but "The fastest integer square root algorithm".

True but as 'forth is hard' would have little traction here we may as
well discuss the other. Were I to tell C users I find it hard, they
would laugh. So it must be my prejudices that is the barrier. 'forth
is hard' isn't so much a fact as it is evangelism - counteracting the
prejudices. Not that I haven't engaged in such myself :)

I'd forgotten about the link Gerry posted. From those only his version
would interest me today as it covers the full unsigned range, consists
only of shifts, and is compact. It doesn't have a remainder. Not sure
how important that is.

[Hans Bezemer]

Post by dxf

...
Sometimes it's not about the destination, but about the voyage. If I wanted to do an item on "the fastest integer square root" algorithm, I wouldn't have called it "Why is Forth so hard", but "The fastest integer square root algorithm".

True but as 'forth is hard' would have little traction here we may as
well discuss the other. Were I to tell C users I find it hard, they
would laugh.

Well, I wouldn't. There are a few peculiarities in C that I find less
than obvious. But then again - I think I would strip C from some
features that I could do without - and add a few in the meanwhile.

Of course, once you master a thing - anything - that becomes so natural
to you that you don't even think about it. But those who are new to the
matter see it with fresh eyes - especially when promises are not fulfilled.

Post by dxf
So it must be my prejudices that is the barrier.

I don't think that's a logical conclusion. Unless you want to define
'prejudices' in the form of 'expectations'. Because I don't think it's
not invalid to see expectations honored. C takes no prisoners. It's
clear about that.

Post by dxf
'forth is hard' isn't so much a fact as it is evangelism - counteracting the
prejudices. Not that I haven't engaged in such myself :)

Forth caught me because of a few things:
1. It was insanely easy to interface with assembly. I remember redoing a
few of Marcel Hendrix string words (Vijgeblad) in assembly;
2. Once I converted the thing to disk, it behaved like it was written
for disk. Even the error messages were read from disk. It transformed it
to a completely new beast. If I'd stuck with Forth long enough to patch
it with a 64 chars routine it'd been perfect for that system.

I first got the internals from a German book (Vögel?). I later dropped
it for C, because it fit my IBM PC needs much better than Forth-83
(yuk!). But if I hadn't been able to create the Forth I liked I don't
think I'd ever revisited Forth.

And that's - in a sense - still true. I'm fascinated by Forth, what it
enabled me to do - and it's that I'm communicating. It's less about
being a huge YT success - or to convert the masses to Forth.

I know that will never happen. We're a dying race. It's not even about
"saving one single person, so he can carry forth the fire". It's more
about me articulating my fascination with this weird language - may be
to try to understand it myself.

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.

Hans Bezemer

[Zong]

Post by Hans Bezemer
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.

[dxf]

...
And that's - in a sense - still true. I'm fascinated by Forth, what it enabled me to do - and it's that I'm communicating. It's less about being a huge YT success - or to convert the masses to Forth.
...
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.

I still remember BASIC code being characterized as 'spaghetti'. FORTRAN was
similarly critiqued for its lack of structure. And of course Forth, its
'stack juggling' and 'write-only' nature. Scratch a little deeper behind
these and one finds someone with an agenda. 'But wait, I have a solution'
they'll tell you.

Off-hand I can't think of newbie forth code that's a disaster such as you've
described. I do recall being impressed by newbies who were plainly serious
about their coding. They may have missed optimizations regular forth coders
would see in a pinch. But certainly none of the mass of ROTs and SWAPs that's
become an [undeserved] cliche for forth coding.

I happened to be revising a medium-sized app. Written several years ago and
essentially undocumented I could still navigate my way around. According to
critics - within and without forth - I shouldn't have been able to read my own
code. The newbie referenced earlier is a professional programmer. I'm not,
and frankly don't have what it would take. What we do have in common is a
fascination with forth such as you mention and a preparedness to give it its
due. Fixing it - not so much. If one can bring intelligence to what one is
doing, as Moore did, that will never conflict.

[Hans Bezemer]

Post by dxf
I still remember BASIC code being characterized as 'spaghetti'. FORTRAN was
similarly critiqued for its lack of structure.

And rightfully so. I once wrote a version of "VENTURE" for my then
"stringless" and "unstructured" uBasic/4tH and it's very hard to read or
maintain. Nowadays it both has strings and structure and those programs
are much easier to read and maintain. I agree there is really something
to it.

Post by dxf
And of course Forth, its
'stack juggling' and 'write-only' nature. Scratch a little deeper behind
these and one finds someone with an agenda. 'But wait, I have a solution'
they'll tell you.

You're claiming here I got an agenda? You're suggesting I think I'm
gonna be a millionaire because - in your eyes - I present "the
definitive solution" to a notorious Forth problem? Really? A nearly dead
language? Because face it: c.l.f is a retirement home.

FYI - I'm not saying that Forth is a "write only" language. I've been
maintaining and expanding (IMHO) non-trivial programs for DECADES.

Post by dxf
Off-hand I can't think of newbie forth code that's a disaster such as you've
described. I do recall being impressed by newbies who were plainly serious
about their coding. They may have missed optimizations regular forth coders
would see in a pinch. But certainly none of the mass of ROTs and SWAPs that's
become an [undeserved] cliche for forth coding.

Vs."The newbie referenced earlier is a professional programmer". That is
"A newbie" not "newbIES". I can't say that has any statistical significance.

And yes, it's undeserved. That was what the whole video was all about, duh!

Post by dxf
I happened to be revising a medium-sized app. Written several years ago and
essentially undocumented I could still navigate my way around. According to
critics - within and without forth - I shouldn't have been able to read my own
code.

I'm not one of them. I made that perfectly clear. I have a simple rule:
if I can't figure out how things work OR I'm unable to maintain it, I
rewrite it. It happened once or twice - and I think it's a good rule.

Hans Bezemer

[dxf]

I still remember BASIC code being characterized as 'spaghetti'.  FORTRAN was
similarly critiqued for its lack of structure.

And rightfully so. I once wrote a version of "VENTURE" for my then "stringless" and "unstructured" uBasic/4tH and it's very hard to read or maintain. Nowadays it both has strings and structure and those programs are much easier to read and maintain. I agree there is really something to it.

Others didn't agree it was a breaking issue and kept on using FORTRAN etc. Apparently
they had developed their own system of management and felt it unnecessary to pursue
each new offering - for there will always be one as knowledge is never complete.

And of course Forth, its
'stack juggling' and 'write-only' nature.  Scratch a little deeper behind
these and one finds someone with an agenda.  'But wait, I have a solution'
they'll tell you.

You're claiming here I got an agenda? You're suggesting I think I'm gonna be a millionaire because - in your eyes - I present "the definitive solution" to a notorious Forth problem? Really? A nearly dead language? Because face it: c.l.f is a retirement home.
...

As would be the case with other Usenet groups that address languages no longer in
vogue. Forth, however, is in a much better position since it doesn't rely on
development teams and a user base to keep them interested. One person alone is
enough to keep it going. It's clear you have a skill when it comes to presentations.
I just felt this one was a little too reliant/accepting of cliches - which has the
effect of confirming them.

[Hans Bezemer]

Post by dxf
I just felt this one was a little too reliant/accepting of cliches - which has the
effect of confirming them.

Well, two things. First, acknowledge that myths are there. It's hard to
debunk a cliche when you deny its existence.. Second, myths don't come
into the world spontaneously. There has to be someone to create them -
and people that pick them up and perpetuate them.

Concerning the first one - it's hard to ignore cliches and on the other
hand to acknowledge them. And you have to acknowledge them to debunk
them. So, let's address a few:

"Forth is hard". When you've mastered it, it's not hard. For that you
have to develop a "feel" for it. That "feel" is very hard to put into
words, because - even if you have recognized some patterns - it's quite
hard to put into solid, easy applicable rules. To quote a Dutch
footballer: "You only get it when you understand it".

But as a newbie who has only been exposed to Fortran/Algol like
languages - it's huge. Because you have to think sequentially while all
your other knowledge concerning programming is based on random access.

I found the same problem when dabbling with Factor - where you have to
design a quotation long before using it. And think in fixed stack
patterns. It really hurts your brain when starting it.

And even when I compare stuff I wrote (more than) a decade ago, I see
I've improved my skills concerning Forth.

So from the viewpoint of a newbie - Forth is hard. From the viewpoint of
a veteran - not so much.

"Forth is a write only language". Maybe I addressed it, but I didn't
consciously debunk it. That was not the purpose of the video. The
purpose of the video was mainly to address the idea why Forth is so hard
to learn - and give some pointers how to tackle an algorithm.

But (again, as a veteran - I think I may claim that title after 30 years
of 4tH) I can't agree to that. Badly written programs are hard to
maintain - no matter in which language they are written.

So consequently, badly written Forth is hard to maintain. I've written
enough non-trivial programs (like uBasic/4tH and the 4tH preprocessor)
which have significantly grown in functionality to know that this is
most certainly not true.

I may do a video on that one later on - because it simply is not true.

"Stack acrobatics" - I think I pretty much tackled that one in the
video. And I think I debunked it more thoroughly than the "Stylish
stack". But maybe I'm mistaken. Don't touch the prophet ;-)

Hans Bezemer

[minforth]

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.

[dxf]

Post by minforth
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.

Who wants to catch users from other languages? It can't be Standard
Forth because that was an exercise in what was the bare minimum number
of forth words one might get away with.

[LIT]

Post by minforth
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?

Post by minforth
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.

- for speed they already have their multicore CPUs
- the size? They don't care about the size that much
in the era of prolific use of "shared libraries" and
GB-sized RAM

So what's the point of transforming Forth into C/Python/whatever,
when one can directly use that C/Python/whatever, when its
offerings are preferred?

[minforth]

Post by LIT

Post by minforth
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?

[LIT]

Post by minforth

Post by LIT
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.

"If you have a lot of small definitions you are writing Forth.
In order to write a lot of small definitions you have to have
a stack. Stacks are not popular. Its strange to me that they
are not. There is a just lot of pressure from vested interests
that don't like stacks, they like registers. Stacks are not a
solve all problems concept but they are very very useful,
especially for information hiding and you have to have two of them."

Charles Moore

[Hans Bezemer]

Post by minforth

Post by LIT

Post by minforth
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?

You, obviously. Since you're so vocal about it. Yes, there are people
who are so eager to pretend they can write Forth, they need loads of
C-isms to prove it (like locals).

Hans Bezemer

[mhx]

Post by LIT

Post by minforth
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

[LIT]

Post by mhx

Post by LIT

Post by minforth
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.

Please, note: I _didn't_ write „it's _all_ what programming
in Forth is about”.

Post by mhx
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.

Indeed.

[dxf]

Post by mhx

Post by LIT

Post by minforth
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.

Nothing I've written in forth could be described as a compiler extension
or DSL. And still I use it. For me it's forth's low-level that appeals
and the knowledge it's me and not some third party that's investigated
the problem and arrived at a solution.

[Hans Bezemer]

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

Oops! Python comes from ABC. ABC has its roots in Algol68 and SETL -
which has its roots in Algol60.

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

Speak for yourself. I don't know how many thousands of lines you have
written - I know how many lines of Forth I've written *WITHOUT* locals.
Can't say it held me down. A case of projection here?

Post by minforth
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.

That's not my intention. I make the compiler I want to use. I write the
stories I want to read. And I make the vids I want to watch. If other
people enjoy them, that's great.

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

As a matter of facts - I didn't care that much about standards. It's a
great way to nick other peoples programs, I agree. But the usability of
a program or library is determined by very different factors, I have
found. My most elaborate (and useful) programs surely aren't easy to
port to vanilla Forth. Still, they're priceless to me, since I pull them
in over and over again.

I don't call that "losing".

Hans Bezemer

[dxf]

Post by Hans Bezemer
...
I know how many lines of Forth I've written *WITHOUT* locals.
Can't say it held me down.

If articles are any indicator, one must go to volume nine of 'Forth Dimensions'
before locals start to get traction. They weren't there at the beginning of Forth -
rather an invention by parties that came later. For forthers the question is whether
the introduction of locals by Forth-94 has made Forth stronger - or weaker?

[a***@spenarnc.xs4all.nl]

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

time to get there.

Post by Hans Bezemer
You can find it at: http://youtu.be/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

Post by Hans Bezemer
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

[dxf]

Post by a***@spenarnc.xs4all.nl
...
And then 'u' . When was the last time you calculate a root between
8FFF,FFFF,FFFF,FFFF and FFFF,FFFF,FFFF,FFFF ?

Do you mean root of a negative number? Not that I can recall.
That leaves two options - an idiot-proof SQRT that checks for
negative inputs, or one that assumes the programmer knows what
he's doing and accepts unsigned.

[Gerry Jackson]

Post by a***@spenarnc.xs4all.nl
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.

[a***@spenarnc.xs4all.nl]

Post by Gerry Jackson

Post by a***@spenarnc.xs4all.nl
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.

Post by Gerry Jackson
--
Gerry

Groetjes Albert

[Gerry Jackson]

Post by a***@spenarnc.xs4all.nl

Post by Gerry Jackson

Post by a***@spenarnc.xs4all.nl
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.

Post by a***@spenarnc.xs4all.nl
I'm happier ignoring those case, than writing tests for them.
Groetjes Albert

I'm happier to not have to ignore any cases

[dxf]

Post by a***@spenarnc.xs4all.nl

Post by Gerry Jackson

Post by a***@spenarnc.xs4all.nl
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.

If one uses operators that are signed then it's already known with a
high degree of certainty it won't work.

[mhx]

dxf wrote:

[..]

Post by dxf
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

Post by dxf
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

[mhx]

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

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

-marcel

[dxf]

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

[mhx]

Post by dxf

\ 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

[a***@spenarnc.xs4all.nl]

Post by mhx

Post by dxf

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

Post by mhx
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.

Post by mhx
-marcel

Groetjes Albert