Main Page | Report Page

 

  Computers Forum Index » Computer Languages (Forth) » What are my options for dictionary hashing?...

Author Message
John Passaniti...
Posted: Thu Sep 30, 2010 9:22 pm
 
On Sep 30, 4:39 pm, Hugh Aguilar <hughaguila... at (no spam) yahoo.com> wrote:
Quote:
This isn't what you said previously:

I'm not sure what specific statement you find in conflict.

You're free to look at the new thread where I posted some results.
Some of those include:

1. That regardless of your inability to understand what a temporal
pattern of access means, a MRU does help significantly, both in the
case of the OP's original dictionary scheme, and in the case of a
simple linear linked list. For extra irony, I'm continuing to use the
Forth code in your "novice" package to illustrate the point.

2. With 16 sublists and the MRU, I'm getting average performance is
better than the worst case of a binary tree. Adding more sublists,
the performance gets much better than a binary tree, and with the MRU
option tossed in, even better still.

I know you have a problem with objective reality, but hey, you're free
to do the same kinds of studies on symtab and blow us all away with
the awesome jaw-dropping performance. Don't think your own Forth code
is a representative dataset? Then I'll be happy to accept any dataset
you care to test against. Unfortunately, the only test you've
provided for symtab so far doesn't tell us much. See, the thing is,
if you're going to suggest using symtab for storing Forth words, you
might want to store some actual Forth words from some actual Forth
code. The current test you provide stores the following stream of
symbols:

goodbye alpha hello tomorrow nobody hello

That might be great as Beat Generation poetry, but it doesn't work so
well as a realistic dataset to test symtab.
 
BruceMcF...
Posted: Sat Oct 02, 2010 9:07 pm
 
On Oct 2, 4:12 pm, "Rod Pemberton" <do_not_h... at (no spam) notreplytome.cmm>
wrote:
Quote:
I was discussing *removing* this field.  You keep discussing DTC, ITC, etc.
*with* the field.

I was referring to the code field as a field containing a pointer to
code, which exists in all ITC code, whether compiled code, created
code, or primitives.

The objection was raised, "oh, no, in DTC its just that the 'code
field' contains code rather than a pointer".

Well, FINE, its a bizarre choice of terminology, but whatever. Then
the "code field" of the primitive is just the primitive.

No matter what you CALL it, no matter whether your CALL it "the code
field" or CALL it "the code", you *still* don't have to POINT TO IT
like you do in ITC, because its DTC, and it gets executed directly.

The actual *fact* that DTC primitives *save an amount of space equal
to the size of the ITC code field* never changes, no matter how people
want to translate terms developed for ITC to DTC.
 
Paul Rubin...
Posted: Sat Oct 02, 2010 10:21 pm
 
Elizabeth D Rather <erather at (no spam) forth.com> writes:
Quote:
The current FEXPM1 looks awful, but there's no nice way to do this in
high level. If someone has one, we will entertain it. It was written
by Andrew Hailey, so I think it's probably perfect Wink
: FEXPM1 ( r -- r )
LOG2(E) F*
FDUP FABS #1.0E F< IF
2**X-1
ELSE
F2** #1.0E F- THEN ; \ (e to the x) - 1

Well, the accuracy of this for small x is going to depend heavily
on how 2**X-1 works. I can only hope 2**X-1 does something reasonable.

There is a smaller speed and accuracy loss from calling 2**X-1 and F2**
at all, instead of computing FEXP and FEXPM1 directly. Maybe that is
a trade-off for code space or the like. But I'm imagining that code
running in simulated floating point on a microcontroller, so the extra
multiplication is rather expensive.
 
George Hubert...
Posted: Sat Oct 02, 2010 11:35 pm
 
On Oct 2, 11:18 pm, Paul Rubin <no.em... at (no spam) nospam.invalid> wrote:
Quote:
Elizabeth D Rather <erat... at (no spam) forth.com> writes:

: FEXPM1 ( r -- r )
    LOG2(E) F*
    FDUP FABS #1.0E F<  IF
      2**X-1
    ELSE
      F2** #1.0E F-  THEN ;  \ (e to the x) - 1

SwiftForth is for PCs.  We almost never do floating point on a
microcontroller.

I had thought the x86 had an FEXP intrinsic, but to my surprise the
basic exponentiation instruction on the x86 is actually F2XM1 which
computes 2**X-1.  So I suspect that your F2** function actually calls
F2XM1 and then adds 1 to the result.  Therefore, unless I'm missing
something, the branch of your FEXPM1 routine where |x| < 1 looks
reasonable but the other part is an abstraction inversion.  That means
you should just get rid of the conditional and let the intrinsic handle
all cases:

   : FEXPM1 ( r -- r ) LOG2(E) F* 2**x-1 ;

Wrong F2XM1 is only guaranteed to give the correct result for |x| < 1
which is the reason for the conditional. F2** is probably implemented
by splitting the number into integer and fractional parts and using
F2XM1
for the fraction and FSCALE for the integer. It's probably (almost
certainly) also used in FEXP. At least that's how W32F, bigForth etc.
do it.

George Hubert
 
Rod Pemberton...
Posted: Sun Oct 03, 2010 12:12 am
 
"BruceMcF" <agila61 at (no spam) netscape.net> wrote in message
news:6dd4acf8-f5d0-4ad0-833e-db92c39e08af at (no spam) q2g2000vbk.googlegroups.com...
Quote:
On Sep 21, 4:20 pm, "Rod Pemberton" <do_not_h... at (no spam) notreplytome.cmm
wrote:
The "code field address" points to the "code field". The contents of the
"code field" is either an address for ITC or an instruction for DTC. In
Forth parlance, the CFA became a synonym for the CF since that's where
it
points to. You can find this usage throughout comp.lang.forth posts, in
sourcecode for Forth's, and articles for Forth.

I was talking about the address in the code field. In DTC, there is
not an address in the code field, there is executable code. So there
is no need for an address in front of a code word, saving two bytes.

I guess you were not objecting to the statement that DTC (and BTC)
saves two bytes with code words, but merely quibbling over the way I
expressed it. For the semantics of the above terms, in DTC, the code
field contains code rather than an address, so the code field
*contains* the primitive word, rather than the address of the
primitive word.


I was discussing *removing* this field. You keep discussing DTC, ITC, etc.
*with* the field.


RP
 
Elizabeth D Rather...
Posted: Sun Oct 03, 2010 1:25 am
 
On 10/2/10 8:21 AM, Paul Rubin wrote:
Quote:
Elizabeth D Rather<erather at (no spam) forth.com> writes:
The current FEXPM1 looks awful, but there's no nice way to do this in
high level. If someone has one, we will entertain it. It was written
by Andrew Hailey, so I think it's probably perfect Wink
: FEXPM1 ( r -- r )
LOG2(E) F*
FDUP FABS #1.0E F< IF
2**X-1
ELSE
F2** #1.0E F- THEN ; \ (e to the x) - 1

Well, the accuracy of this for small x is going to depend heavily
on how 2**X-1 works. I can only hope 2**X-1 does something reasonable.

There is a smaller speed and accuracy loss from calling 2**X-1 and F2**
at all, instead of computing FEXP and FEXPM1 directly. Maybe that is
a trade-off for code space or the like. But I'm imagining that code
running in simulated floating point on a microcontroller, so the extra
multiplication is rather expensive.

SwiftForth is for PCs. We almost never do floating point on a
microcontroller. There are excellent fixed-point algorithms available
that are much faster (and sometimes more correct).

Cheers,
Elizabeth

--
==================================================
Elizabeth D. Rather (US & Canada) 800-55-FORTH
FORTH Inc. +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================
 
Paul Rubin...
Posted: Sun Oct 03, 2010 2:18 am
 
Elizabeth D Rather <erather at (no spam) forth.com> writes:
Quote:
: FEXPM1 ( r -- r )
LOG2(E) F*
FDUP FABS #1.0E F< IF
2**X-1
ELSE
F2** #1.0E F- THEN ; \ (e to the x) - 1

SwiftForth is for PCs. We almost never do floating point on a
microcontroller.

I had thought the x86 had an FEXP intrinsic, but to my surprise the
basic exponentiation instruction on the x86 is actually F2XM1 which
computes 2**X-1. So I suspect that your F2** function actually calls
F2XM1 and then adds 1 to the result. Therefore, unless I'm missing
something, the branch of your FEXPM1 routine where |x| < 1 looks
reasonable but the other part is an abstraction inversion. That means
you should just get rid of the conditional and let the intrinsic handle
all cases:

: FEXPM1 ( r -- r ) LOG2(E) F* 2**x-1 ;
 
Andrew Haley...
Posted: Sun Oct 03, 2010 1:46 pm
 
Elizabeth D Rather <erather at (no spam) forth.com> wrote:
Quote:
The current FEXPM1 looks awful, but there's no nice way to do this
in high level. If someone has one, we will entertain it. It was
written by Andrew Hailey, so I think it's probably perfect Wink

:-P

Andrew.
 
Andrew Haley...
Posted: Sun Oct 03, 2010 1:53 pm
 
Paul Rubin <no.email at (no spam) nospam.invalid> wrote:
Quote:
Elizabeth D Rather <erather at (no spam) forth.com> writes:
The current FEXPM1 looks awful, but there's no nice way to do this in
high level. If someone has one, we will entertain it. It was written
by Andrew Hailey, so I think it's probably perfect Wink
: FEXPM1 ( r -- r )
LOG2(E) F*
FDUP FABS #1.0E F< IF
2**X-1
ELSE
F2** #1.0E F- THEN ; \ (e to the x) - 1

Well, the accuracy of this for small x is going to depend heavily
on how 2**X-1 works. I can only hope 2**X-1 does something reasonable.

It's accurate to 1 ulp, using the 80-bit format, but covers only the
range -1 <= x < 1.

Quote:
There is a smaller speed and accuracy loss from calling 2**X-1 and F2**
at all, instead of computing FEXP and FEXPM1 directly.

How would you compute FEXPM1 directly? No approximation can hope to
cover the whole range of exp(x), so some sort of range reduction is
required. It's conventional (pretty near universal) to do it in the
number base used by the floating-point arithmetic, and convert to the
base required by the caller as required.

Andrew.
 
Andrew Haley...
Posted: Sun Oct 03, 2010 2:01 pm
 
Paul Rubin <no.email at (no spam) nospam.invalid> wrote:
Quote:
Elizabeth D Rather <erather at (no spam) forth.com> writes:
: FEXPM1 ( r -- r )
LOG2(E) F*
FDUP FABS #1.0E F< IF
2**X-1
ELSE
F2** #1.0E F- THEN ; \ (e to the x) - 1

SwiftForth is for PCs. We almost never do floating point on a
microcontroller.

I had thought the x86 had an FEXP intrinsic, but to my surprise the
basic exponentiation instruction on the x86 is actually F2XM1 which
computes 2**X-1. So I suspect that your F2** function actually calls
F2XM1 and then adds 1 to the result. Therefore, unless I'm missing
something

You're missing something. :-)

Have a look at the part of the specification that mentions the range
of x in F2XM1.

Andrew,
 
Paul Rubin...
Posted: Sun Oct 03, 2010 7:37 pm
 
Andrew Haley <andrew29 at (no spam) littlepinkcloud.invalid> writes:
Quote:
How would you compute FEXPM1 directly? No approximation can hope to
cover the whole range of exp(x), so some sort of range reduction is
required. It's conventional (pretty near universal) to do it in the
number base used by the floating-point arithmetic, and convert to the
base required by the caller as required.

Thanks for all the responses. For some reason I thought the x86 had
separate intrinsics for FEXP and FEXPM1 and that these did appropriate
range reductions already, like FSIN and FCOS do.

I also have been under the impression that for machines with no floating
point and no hardware multiplication, FEXP is usually done with the
identity exp(x) = sinh(x) + cosh(x) where sinh and cosh are computed
with CORDIC. Maybe this too is wrong. Obviously that also needs range
reduction but the point is that it uses base e directly. With a
multiplier, it just seems natural to use separate polynomial or rational
approximations to 2**x and exp(x) if you want both functions, unless
you're cramped for code space.

A little bit of web surfing finds an interesting-looking book about
elementary function evaluation that I might try to get from the library:

http://perso.ens-lyon.fr/jean-michel.muller/SecondEdition.html
 
Elizabeth D Rather...
Posted: Mon Oct 04, 2010 5:16 am
 
On 10/3/10 5:37 AM, Paul Rubin wrote:
Quote:
Andrew Haley<andrew29 at (no spam) littlepinkcloud.invalid> writes:
How would you compute FEXPM1 directly? No approximation can hope to
cover the whole range of exp(x), so some sort of range reduction is
required. It's conventional (pretty near universal) to do it in the
number base used by the floating-point arithmetic, and convert to the
base required by the caller as required.

Thanks for all the responses. For some reason I thought the x86 had
separate intrinsics for FEXP and FEXPM1 and that these did appropriate
range reductions already, like FSIN and FCOS do.

I also have been under the impression that for machines with no floating
point and no hardware multiplication, FEXP is usually done with the
identity exp(x) = sinh(x) + cosh(x) where sinh and cosh are computed
with CORDIC. Maybe this too is wrong. Obviously that also needs range
reduction but the point is that it uses base e directly. With a
multiplier, it just seems natural to use separate polynomial or rational
approximations to 2**x and exp(x) if you want both functions, unless
you're cramped for code space.

A little bit of web surfing finds an interesting-looking book about
elementary function evaluation that I might try to get from the library:

http://perso.ens-lyon.fr/jean-michel.muller/SecondEdition.html

FORTH, Inc. has for many years relied on this wonderful book for doing
high-powered math on computationally-challenged microprocessors:

Hart, John F.; et al (1968). Computer approximations. New York: John
Wiley & Sons, Inc. ISBN 0882756427 (there's a 1978 2nd ed.).

It's old, but mathematics hasn't changed much since 1968. Both eds are
also often out of print, but sometimes findable by googleing or on eBay.

See this two-part article:

http://www.eetimes.com/discussion/break-point/4025654/Approximating-reality
http://www.eetimes.com/discussion/break-point/4025669/Approximations-part-deux

Our SwiftX cross-compilers include libraries for some common functions
using these algorithms.

Cheers,
Elizabeth

--
==================================================
Elizabeth D. Rather (US & Canada) 800-55-FORTH
FORTH Inc. +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================
 
Andrew Haley...
Posted: Thu Oct 07, 2010 1:54 pm
 
Paul Rubin <no.email at (no spam) nospam.invalid> wrote:
Quote:
Albert van der Horst <albert at (no spam) spenarnc.xs4all.nl> writes:

CORDIC : primitive hardware without floating point
Chebychev approximations (poly's) : has long been state of the art
Quotient of two polynomials : now state of the art
Polynomials have the disadvantage that they don't work well
near a pole in the complex plane, the quotients don't have that
disadvantage.

Using quotients (Pade approximants, say) isn't even slightly new;
the trade-off usually is in favor of polynomials because division is
much more expensive than multiplication, so you can compute quite a
few more polynomial terms for the cost of computing a quotient.

Sure, but that doesn't help at all if the function you're trying to
approximate is inherently nonpolynomial -- as Albert said, anything
with a pole, infinite derivatives, and so on. For elementary
functions this isn't a problem, with the obvious exception of tan(x).
And there, you have to use a ratio: there's no getting away from it.

Maybe, now that designers have so many transistors to play with, we'll
be getting fast division units. It's not as if there's any great
mystery about how to do it. [1]

Andrew.

[1] High-Performance Floating Point Divide Albert A. Liddicoat and
Michael J. Flynn Euromicro Symposium on Digital System Design pages
354-361, Warsaw, Poland, September 2001.
ftp://arith.stanford.edu/tr/12_liddicoat_a.pdf
 
 
Page 13 of 13    Goto page Previous  1, 2, 3 ... 11, 12, 13
All times are GMT
The time now is Sun Apr 20, 2014 12:55 am