From: Mathieu Bouchard <matju@...>
Date: 2001-01-04T06:45:47+09:00
Subject: [ruby-talk:8597] Re: speedup of anagram finder

> 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)) ,
[...]
> ( i.e, the numbers I used are 10^7 * log(p), for the first 26 primes, using
> Math#log )
> 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:

Try this strategy:
1. Use an algorithm that gives erroneous results but is very fast
2. Use a postprocessing algorithm that corrects the results.

If you don't worry too much about avoiding collisions in your current
algorithm, then you might be able to accelerate it quite a bit. This will
give you a small number of false positives. To find them, then on any set
of anagrams you have to perform a test that is exact but slow. Its
slowness won't be a problem because the test is only run on a few small
subsets of the original set.

I think however that using naturals below 10**7 is already quite fast
because you stay well under one billion (Fixnum maximum) with normal
words. 

matju