HDTenEightyP/NetNews huggingface dataset:
From: jos@and.nl (Jos Horsmeier)
Newsgroups: comp.programming
Subject: Re: Soundex algorithms, database indexing
Keywords: soundex, databases, indexing
Date: 24 Jul 92 12:20:17 GMT
Organization: AND Software BV Rotterdam

[ I've tried to mail you, but it bounced, so I post it here ... ]

In article <1992Jul22.122831.27758@cbnews.cb.att.com> Marc@cbnews.cb.att.com writes:
|Hello programmers/researchers,

	[ names stored in a database ... ]

|	For the latter one I want to set up a soundex key as well.  I have heard	of the soundex algorithm but never seen any pratical applications.

|	I would like to get info/ a 'C' program (function) that makes use of
|	the Soundex algorithm.

|	Also any information on using index files (for fast searching) or
|	'C' code would be greatly appreciated.

Basically, the Soundex algorithm goes like this:

- Chop the first character from the name

- Map all the letters according to the following table:

	- b, f, p, v	         ---> 1
	- c, g, j, k, q, s, x, z ---> 2
	- d, t                   ---> 3
	- l                      ---> 4
	- m,n                    ---> 5
	- r                      ---> 6
	- a, e, h, i, o, u, w, y ---> 7

- Where ever a sequence of the equal digits occur, remove them all but
  the first of the sequence

- Optionally, chop the first digit from the number

- Optionally, remove all sevens (all vowels)

- Add some 0's at the end (dependent on the number `n' in the next step)

- Take the first n digits and prepend the letter from the first step.

The table, given in step 2 is highly language dependent of course,
e.g. in Dutch a dental `t' might be pronounced as a dental `s' and
certain combinations of vowels result in different diphtongues.

So, transform all names into their Soundex form and compare the
two results for equality. That's all there is to it ...

About your question on indexes: I'd suggest a hashing scheme if it's
unlikely that records will be removed from the database frequently.
On the other hand, a B-tree will do fine too here.

kind regards,

Jos aka jos@and.nl

Newsgroups: comp.programming
From: gideony@microsoft.com (Gideon Yuval)
Subject: Re: finding 1st one in integer
Date: 22 Jul 92 06:51:11 GMT
Organization: Microsoft Corporation

A 37-entry table suffices.

table[ ( (X xor (X-1)) modulo 37 ] will get you the 1st 1-bit
from the bottom.
-- 
Gideon Yuval, gideony@microsoft.com, 206-882-8080 (fax:-883-8101;TWX:160520)
Newsgroups: comp.programming
From: berlin@is.morgan.com (Alexander Berlin)
Subject: Re: Does "400% faster" make sense? (Was: Re: finding 1st one in integer)
Organization: Morgan Stanley - IS
Date: Wed, 22 Jul 1992 21:23:37 GMT

In article <LOWRY.92Jul22154231@rotor.watson.ibm.com>, lowry@watson.ibm.com (Andy Lowry) writes:
|> In article <1992Jul22.120735@is.morgan.com> berlin@is.morgan.com (Alexander Berlin) writes:
|>  > Just a side note: it's impossible to have code that runs 400% faster. Twice
|>  > as fast means 50% faster. 100% faster means in NO TIME.
|>  > 400% slower makes sense, 400% faster doesn't.
|>  > 4 times faster means 75% faster.
|> 
|> Hmm... did somebody issue an edict on this of which I wasn't aware (or
|> was this the edict itself :-)?  I know these are confusing terms that

Must be your math teacher :)

|> are vague because they are used differently by different people, but I
|> can make a perfectly good case for saying that "400% faster" should
|> mean "at 400% the speed," i.e. "at four times the speed."  Or maybe
|> I'd prefer to say that "400% faster" means "at a speed that is 400%
|> greater" which means "at five times the speed."  This is also in line
|> with what I would expect a "400% speedup" to mean.  I certainly would
|> think it confusing if making something 75% faster were to result in a
|> 300% speedup!
|> 
|> Your rule appears to be that if measured time is cut to x% of the
|> original, then you call it "(100-x)% faster" if x < 100 and (I'm
|> guessing) "x% slower" if x > 100.  But "fast" is a word that I
|> associate with speed, not time, so even if the world were to vote on
|> what these phrases were supposed to mean, I don't think I'd vote for
|> your definitions!
|> 
|> And if the world doesn't vote and start using consistent definitions,
|> then your side note is pretty much without value (or perhaps of
|> negative value because of its misleading statements), since it doesn't
|> help me one iota in reading literature that makes use of such phrases.
|> I still have to rely on either a precise definition made up front by
|> the author, or on being able to deduce the intended meaning from
|> context, because I certainly can't assume that the author is following
|> your conventions!
|> 
|> It's much better to point out the inherent vagueness in these terms as
|> they are used in practice, and encourage people to include precise
|> definitions when needed, than to claim that there's some universally
|> accepted precise definition when there isn't.

If some job takes me 100 seconds and you can do it in 25 seconds:
I am 300% slower then you are.              (100-25)/25*100 
You are 75% faster than I am(not 300)       (100-25)/100*100
Your performance is 400% of mine.           (1/25)/(1/100)*100
My performance is 25% of yours.             (1/100)/(1/25)*100

And yes, to do the job 75% faster (in 75% less time) you need to increase your 
performance by 300%. Vote is not required here.
|> --
|> Andy Lowry, lowry@watson.ibm.com, (914) 784-7925
|> IBM Research, P.O. Box 704, Yorktown Heights, NY  10598
---
Alex Berlin                     
berlin@is.morgan.com
Newsgroups: comp.programming
From: casper@fwi.uva.nl (Casper H.S. Dik)
Subject: Re: finding 1st one in integer
Organization: FWI, University of Amsterdam
Date: Wed, 22 Jul 1992 22:17:01 GMT

berlin@is.morgan.com (Alexander Berlin) writes:

>In article <1992Jul22.152827.14267@cs.cornell.edu>, ressler@cs.cornell.edu (Gene Ressler) writes:

>|> ....
>|> benchmark code (chris torek?), this runs about 400% faster than the 37 element
>|> ....

>Just a side note: it's impossible to have code that runs 400% faster. Twice
>as fast means 50% faster. 100% faster means in NO TIME.
>400% slower makes sense, 400% faster doesn't.
>4 times faster means 75% faster.

I beg your pardon!? Can some thing be twice as fast? Three times?
Four times faster? Five times faster? If someone says
``method X is n% y-er'', he really means 'X is (n/100+1) times y-er'.
Or 400% faster translates to 5 times faster, which looks plausible
enough.

Casper
-- 
						|	Casper H.S. Dik
						|	casper@fwi.uva.nl
Newsgroups: comp.programming
From: hrubin@pop.stat.purdue.edu (Herman Rubin)
Newsgroups: comp.programming
Subject: Re: floating point routines with double precision
Date: 23 Jul 92 22:38:16 GMT
Organization: Purdue University Statistics Department

In article <1992Jul22.120724.3466@druid.uucp> darcy@druid.uucp (D'Arcy J.M. Cain) writes:
>hrubin@pop.stat.purdue.edu (Herman Rubin) writes:
>>Use assembler for you particular machine if you want any speed.  Even 
>>setting it up for the compiler will be a major headache, and you will
>>have just as many problems with object size.

>Here is how I set up my compiler to generate machine code for a floating
>point operation:

>    result = value/4.586;    /* Well it does   :-) */

>Seriously, there may be cases where the compiler doesn't give the fastest
>code for a given operation but they are probably the rare exception.  With
>modern compilers the chances are that hand coded assembly won't be as fast
>and are certainly longer to program.  A much better method of speeding up
>critical sections of code is inlining.  That's why the current Gnu compiler
>internally inlines some of the more common string functions.  Function
>call overhead is still relatively expensive on most popular CPUs.

It depends on what you call double precision.  The IEEE standard
double precision probably should be called single precision, and
what it calls single precision should be called half precision.

Now I was answering the question assuming that more than the designed
precision is needed.  The routines are not difficult for a human to
design, but almost hopeless for a compiler.  Anyone who writes such
a procedure for a machine which has forced normalization will curse
the designers.
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
Phone: (317)494-6054
hrubin@pop.stat.purdue.edu (Internet, bitnet)  
{purdue,pur-ee}!pop.stat!hrubin(UUCP)
Newsgroups: comp.programming,comp.unix.programmer,alt.msdos.programmer,comp.databases
From: eotto@cbnews.cb.att.com (erick.otto)
Subject: Database 'C' library.
Organization: AT&T
Date: Fri, 24 Jul 1992 16:24:04 GMT
Followup-To: poster
Keywords: DataBase library, Turbo-c,


All of you out there,

	I would like to find a library that contains DB routines. Like add a 		item to the database, retrieve item, etc etc, For the turbo 'C' compiler	or any other library as long as it contains the source code.

	I can ftp to most sites, does anybody know of a free one.

	I have had a look at something called KSLIB but that does not work for
	me. and it does not contain source code.


	P.S. For all of you that mailed me on the Soundex algorithm, Thanks a 
	      lot, I know have about 5 different 'C' programs that I am still
             looking into. (Luckily they all produce the same soundex key)
	     pretty good guys. And I will be posting my findings to these groups	     very soon.


Erick Otto
eotto@hvlpa.att.com
eotto@cbnews.att.com
From: morse@cs.unc.edu (Bryan Morse)
Newsgroups: comp.programming
Subject: Re: Does "400% faster" make sense? (Was: Re: finding 1st one in integer)
Date: 27 Jul 92 20:10:10 GMT

In article <KERS.92Jul23082251@cdollin.hpl.hp.com>, kers@hplb.hpl.hp.com (Chris Dollin) writes:
|> Surely 75% faster means at 75/100 == 3/4 of the speed, ie 4/3 ~= 133% of the
|> time, ie *slower*? 

Not quite.  75% *as fast* does mean 3/4 of the speed.  75% *faster* 
means 175% or 7/4 of the speed.

Think of it this way: 
 I am running at 100% of my speed (obviously).
 You are running 75% faster or 100% + 75% = 175% of my speed.

Or another example:

 I am driving at 50 mph.
 You are driving at 55 mph.

 You are going 55-50 = 5 mph faster than me.
 5 mph is 10% of my speed.
 Therefore, you are going 10% (of my speed) faster than me.

 I am going 5 mph slower than you.
 5 mph is approximately 9% (1/11) of your speed.
 Therefore, I am going approximately 9% (of your speed) slower than you.

The lack of symmetry between faster and slower has lead some (e.g., 
Hennessy and Patterson) to choose only to refer to the faster one as 
XX% faster than the slower one, never the other way around.

-- 
Bryan Morse                University of North Carolina at Chapel Hill
morse@cs.unc.edu           Department of Computer Science
From: pdh@netcom.com (Phil Howard )
Newsgroups: comp.programming
Subject: Re: finding 1st one in integer
Date: 24 Jul 92 18:31:33 GMT
Organization: Netcom - Online Communication Services  (408 241-9760 guest)

ressler@cs.cornell.edu (Gene Ressler) writes:

>In article <1992Jul22.120735@is.morgan.com> berlin@is.morgan.com (Alexander Berlin) writes:

>>Just a side note: it's impossible to have code that runs 400% faster. 

>Of course.  Silly mistake.  I meant 4 times as fast.

I've made code run 400% faster before.  But it was 5 times as fast.
-- 
/***********************************************************************\
| Phil Howard  ---  KA9WGN  ---  pdh@netcom.com   |   "The problem with |
| depending on government is that you cannot depend on it" - Tony Brown |
\***********************************************************************/
From: hrubin@pop.stat.purdue.edu (Herman Rubin)
Newsgroups: comp.programming
Subject: Compilers: was: Re: Advantages/disadvantages of macros/inlining?
Keywords: macro inline
Date: 23 Jul 92 22:33:38 GMT
Organization: Purdue University Statistics Department

In article <1992Jul22.154647.877@tc.fluke.COM> kurt@tc.fluke.COM (Kurt Guntheroth) writes:
>hrubin@pop.stat.purdue.edu (Herman Rubin) writes:

>>On the one hand, computer people are stupidly insisting that the
>>compiler can do all, and that human attempts to improve what compilers
>>can do are futile.  Now we hear the complaint that the compiler will
>>choke on the problem.

>>On the one hand, we hear that there are lots of registers.  On the
>>other hand, we hear that there are not enough for inlining.

>>Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399

>Well, it's all true.

>On a large program, a world-class compiler can do far better than even an
>experienced programmer at discovering optimizations.  I would expect the
>compiler to win every time on non-toy problems.

The compiler can only do the optimizations is knows about.  If the human is
restricted to such weak things as Fortran or C, a world-class compiler 
would win most of the time.  But there are quite a few things which the
HLLs are unable to do anything reasonable with.

>On some RISC processors, there are virtually unlimited registers; hundreds
>of them.

One of the people in the computing center here told me that even the
CISC Cyber 205, with its 256 registers, about 240 useful by the programs,
sometimes runs out.  It also has relatively fast load/store of register
blocks.

>On the other hand, there are constructs (like inlining) that can make it
>more difficult for some compilers to do a good job.  Are these world class
>compilers?  Maybe and maybe not, but it doesn't rob the truth from the first
>assertion.  The best compilers on the best machines translating appropriate
>languages can do far better than a human.

>And there are machines with absolutely miserable register sets, and
>compilers with code generation strategies optimized for machines with many
>registers often suck big-time on machines with few or difficult-to-use
>registers.

But the compilers, even the world class ones, are woefully ignorant.  Of
course, the answer is to let the human instruct the compiler, and the 
instruction may have to be to try out this large variety of procedures.
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
Phone: (317)494-6054
hrubin@pop.stat.purdue.edu (Internet, bitnet)  
{purdue,pur-ee}!pop.stat!hrubin(UUCP)
From: dave@cs.arizona.edu (Dave Schaumann)
Newsgroups: comp.programming
Subject: Re: Calculating a cube root
Date: 21 Jul 92 21:02:07 GMT
Reply-To: dave@cs.arizona.edu (Dave Schaumann)
Organization: University of Arizona

In article <1992Jul21.085023.11890@cs.ruu.nl>, jeroen@cs (Jeroen Fokker) writes:
>dave@cs.arizona.edu (Dave Schaumann) had some remarks about my
>cuberoot-program.
>
>>> #define EPSILON 0.00001
>
>>  which of course limits the accuracy quite severly.
>
>The nice thing about #defined constants is that you can
>adapt them to your needs. 

Of course, making EPSILON smaller will also increase the inefficiency of
your algorithm.  (The point being, I suppose, that no such trade-off is
required by using the library routines.)

>>> return( a-b<EPSILON && b-a<EPSILON );
>
>> This expression will always yield 0.
>
>Nice try for an insult, but not justified.

Mea culpa.  After careful observation, I see that your code is correct
(tho not at all clear, IMHO).  I would've greatly preferred

	#define abs(x) ((x) > 0 ? (x) : (-x))

	  . . .

	return abs(a-b) < EPSILON ;

>Speaking of correctness: try and calculate cubert(0.0)
>using exp(log(x)/3.0).

No thanks; I'm driving.

-- 
You unlock this door with the key of imagination.  Beyond it is another
dimension: a dimension if sound, a dimension of sight, a dimension of mind.
You're moving into a land of both shadow and substance, of things and ideas.
You've just crossed over into... the Twilight Zone.
Newsgroups: comp.programming
From: jeroen@cs.ruu.nl (Jeroen Fokker)
Subject: Re: Calculating a cube root
Date: Wed, 22 Jul 1992 08:16:58 GMT
Organization: Utrecht University, Dept. of Computer Science

This thread is floating away from the original subject a bit,
but let me add just one posting to it.

I suggested the following code for "approximate-equal-to":

>>>> return( a-b<EPSILON && b-a<EPSILON );

Dave Schaumann (dave@cs.arizona.edu) first claimed that this
was incorrect, then retracts his claim, but remarks:

> After careful observation, I see that your code is correct
> (tho not at all clear, IMHO).  I would've greatly preferred
>
>       #define abs(x) ((x) > 0 ? (x) : (-x))
>       return abs(a-b) < EPSILON ;

This may be more clear, but alas, it is not correct.
A classic pitfall with macroexpansion: abs(1-1) yields
-2 this way.

Now for some obligatory programming:
you can apply Newton's method to find the inverse of _any_
function f by iterating:

     b - (f(b)-x)/f'(b)

where f' is the derivative of f.
The starting value of b depends on the function at hand.
For monotonic f, x will do most times.
Of course, f should be differentiable.
If f is not monotonic, the iteration may not terminate.

Formulas for sqareroot and cuberoot are special cases:

For sqrt,   iterate  b - (b^2-x)/2b,   that is (b+x/b)/2
For cubert, iterate  b - (b^3-x)/3b^2, that is (2b+x/b^2)/3
For arcsin, iterate  b - (sin(b)-x)/cos(b).

--
Jeroen Fokker                                 |  jeroen@cs.ruu.nl
dept.of Computer Science, Utrecht University  |  tel.+31-30-534129
PObox 80089, 3508TB Utrecht, the Netherlands  |  fax.+31-30-513791

Newsgroups: comp.programming
From: berlin@is.morgan.com (Alexander Berlin)
Subject: Re: finding 1st one in integer
Organization: Morgan Stanley - IS
Date: Wed, 22 Jul 1992 16:07:35 GMT

In article <1992Jul22.152827.14267@cs.cornell.edu>, ressler@cs.cornell.edu (Gene Ressler) writes:

|> ....
|> benchmark code (chris torek?), this runs about 400% faster than the 37 element
|> ....

Just a side note: it's impossible to have code that runs 400% faster. Twice
as fast means 50% faster. 100% faster means in NO TIME.
400% slower makes sense, 400% faster doesn't.
4 times faster means 75% faster.
---
Alex Berlin                     
berlin@is.morgan.com
From: norman@a.cs.okstate.edu (Norman Graham)
Newsgroups: comp.programming
Subject: Re: 400% makes sense
Date: 25 Jul 92 18:42:59 GMT
Organization: Oklahoma State University

From article <1992Jul25.171314.22419@uwm.edu>, by markh@csd4.csd.uwm.edu (Mark William Hopkins):
> 20,000,000 operations/second is 400% of 5,000,000 operations/second.
> 
> Case closed.

Not exactly. 400% is a nonsensical term. Percent (%) means 'per hundred' or
'of each hundred', and thus is only meaningful for values between 0 and
100 (inclusive). Percent is best used for absolute measurements, rather
than relative comparisons such as the above example.

The use of percent in relative comparisons naturally leads to subtle
misunderstandings.  Thus its best to say something like "machine A
(at 20 M op/sec) is four times as fast as machine B (at 5 M op/sec)."
-- 
Norman Graham
<norman@a.cs.okstate.edu>                 Standard Disclaimer Applies
From: nessett@llnl.gov (Danny M. Nessett)
Newsgroups: comp.programming
Subject: Tutorials or Texts on how to write a debugger
Date: 22 Jul 92 23:56:27 GMT
Organization: LLNL

I am not a regular reader of this news group, but I have looked through the
most recent postings and have not found the answer to the following question.
Are there any tutorials or texts that discuss how to build a debugger? I am
interested in the general issues, architecture, data structures, algorithms,
etc. that one needs to create a useful debugger. Please email me directly
with any response, since as I said I do not regularly read this group.

Thanks in advance to anyone who can help.

Dan Nessett
From: martin@matilda.vut.edu.au (Martin Schweitzer)
Newsgroups: comp.programming
Subject: Finding integer square root
Date: 24 Jul 92 07:17:04 GMT
Reply-To: martin@matilda.vut.edu.au (Martin Schweitzer)
Organization: Victoria University of Technology, Melb, Australia

I'm looking for an efficient algorithm that will find the highest integer
  x such that x * x < n for some given integer n.

Of course there are some brute force methods, but I seem to
recall coming across an algorithm once in a text about
proving correctness.

Martin
From: paj@uk.co.gec-mrc (Paul Johnson)
Newsgroups: comp.programming
Subject: Re: Spreadsheet data structures
Date: 31 Jul 92 08:29:55 GMT
Reply-To: paj@uk.co.gec-mrc (Paul Johnson)
Distribution: comp
Organization: GEC-Marconi Research Centre, Great Baddow, UK

In article <PK.92Jul30095458@talitiainen.cs.tut.fi> pk@cs.tut.fi (Kellom{ki Pertti) writes:
>Does anyone know what kind of data structures are used for storing
>spreadsheet data?

Use a hash table.  That way you get constant time access and unlimited
sheet size.

Paul.
-- 
Paul Johnson (paj@gec-mrc.co.uk).	    | Tel: +44 245 73331 ext 3245
--------------------------------------------+----------------------------------
These ideas and others like them can be had | GEC-Marconi Research is not
for $0.02 each from any reputable idealist. | responsible for my opinions
Newsgroups: comp.programming
From: rosauer@fzi.de (Bernd Rosauer)
Subject: greedy algorithms
Organization: FZI Forschungszentrum Informatik, Karlsruhe, Germany
Date: Thu, 30 Jul 1992 17:23:36 GMT

Does anyone know a textbook or survey paper about greedy algorithms?

--Bernd

From: scole@hpcupt3.cup.hp.com (Scott Cole)
Date: Wed, 29 Jul 1992 18:19:11 GMT
Subject: THINK C ANY ONE????
Organization: Hewlett Packard, Cupertino
Newsgroups: comp.programming

My Think C strxxx functions aren't working correctly. Any one
have any suggestions?

Thanks Alot in advance,
Scott Cole

PS if you can solve my problem I'll buy you lunch.
Newsgroups: comp.programming
From: joeb@moci.uucp (Joe Bronikowski (Little Joe))
Subject: Re: Finding integer square root
Organization: ICOM, Inc., West Allis, WI
Date: Mon, 27 Jul 92 19:22:23 GMT
Summary: recommend Embedded Systems Programming magazine

In article <1992Jul24.071704.6698@matilda.vut.edu.au> martin@matilda.vut.edu.au (Martin Schweitzer) writes:
>I'm looking for an efficient algorithm that will find the highest integer
>  x such that x * x < n for some given integer n.
>
>Of course there are some brute force methods, but I seem to
>recall coming across an algorithm once in a text about
>proving correctness.
>
>Martin

I suggest looking in back issues of _Embedded Systems Programming_, a monthly
magazine.  A long series of articles by Jack Crenshaw goes into excruciating
detail in developing simple, fast, reliable algorithms for square roots,
tangential functions, etc., with integer and floating-point examples.  It makes
VERY interesting reading.  If you can't find this magazine in Austrailia,
you can contact them at:

	Embedded Systems Programing
	Miller Freeman, Inc.
	600 Harrison St.
	San Francisco, CA 94107
	1-800-950-0523

	(ISSN 100-3272, if you need it)

If you can't get the info any other way, mail me and I'll type in the
algorithm you need.  I strongly recommend reading the articles though,
since the algorithm development is so neat :-)

By the way, this magazine gives out free subscriptions to engineers/programmers
in the embedded control field, so you might ask for a subscription
qualification form.
-- 
     //	   |------+---,				Joe Bronikowski
 \\ //	   |      |    )			ICOM, Inc.
  \X/	   |------+---'				...!uwm.edu!moci!joeb
From: kers@hplb.hpl.hp.com (Chris Dollin)
Date: Thu, 23 Jul 1992 07:22:51 GMT
Subject: Re: Does "400% faster" make sense? (Was: Re: finding 1st one in integer)
Organization: Hewlett-Packard Laboratories, Bristol, UK.
Newsgroups: comp.programming

In article ... berlin@is.morgan.com (Alexander Berlin) writes:

   If some job takes me 100 seconds and you can do it in 25 seconds:
   I am 300% slower then you are.              (100-25)/25*100 
   You are 75% faster than I am(not 300)       (100-25)/100*100
   Your performance is 400% of mine.           (1/25)/(1/100)*100
   My performance is 25% of yours.             (1/100)/(1/25)*100

   And yes, to do the job 75% faster (in 75% less time) you need to increase 
   your performance by 300%. Vote is not required here.

Surely 75% faster means at 75/100 == 3/4 of the speed, ie 4/3 ~= 133% of the
time, ie *slower*? 
--

Regards,    | ``In fingers of trees, and valleys of gold    | Judy Tzuke
Kers.       | I watch as you outshine the charlatan foe.''  | Higher & Higher