[ruby-talk:8508] Re: speedup of anagram finder

> go, either. The fact is, I've spent a lot of time the past couple days
> thinking about
> a new solution, related to the "primes" solution. If I come up with
> something 

Here's a faster, but obviously problematic, solution, kind of a first
approximation for a solution:

Again, if you don't like math, I apologize for any jargon in the following
text.

I call it the "slide rule" approach. "prime" was slowing up because of the
way Ruby was handling
multiplication of large numbers. So I thought about a logarithmic solution
using

[x] = [y] iff s(x) = s(y) iff log(s(x)) = log(s(y)) ,

where [x] is the equivalence class of x using the anagram relation and s(x)
is an index function
like that produced by asc2prime. Forgive rounding error for the moment. This
approach works on
the first 10K words in /usr/dict/words and runs fast:


unpack      0.961000   0.000000   0.961000 (  0.962000)
prime3      1.172000   0.000000   1.172000 (  1.172000)
sliderule   0.841000   0.000000   0.841000 (  0.841000)

Here's part of the array I used:

         asc2log = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
                      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
                      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
                      0,0,0,0,0,6931471,10986122,16094379,

( i.e, the numbers I used are 10^7 * log(p), for the first 26 primes, using
Math#log )

and I made the following 2 obvious changes in the algorithm:  
         
          key = 0
           word.each_byte {|s| key += asc2log[s]} 



I don't think there's a future for this solution, but it got me thinking
about diophantine solutions to
this problem, just because sums are computed faster than products. Yesterday
I started thinking
about limiting and defining the problem this way:

Let n = number of letters in an "alphabet"
Let m = maximum number of letters in a word

Find an equation 

a1X1 + ... + anXn = 0

 so that the solution set does not contain anything that could break the
algorithm that computes the
integral index I want. 

Trivial first case: n = 2.  a1 = 1, a2 = m + 1 works.

Any feedback would be appreciated.

Barry