in reply to Re^5: OT: Finding Factor Closest To Square Root
in thread OT: Finding Factor Closest To Square Root

This discussion and my own (preliminary) benchmarking results have led me to rethink a few things about my real problem.

For instance, when computing F(n), we can make use of the addition formula to break n into 2 pieces: 

F(n) = F(i+j) = F(i-1)*F(j) + F(i)*F(j+1)

[download]
Then: 
j = k**2 = int(sqrt(n))
i = n - j
F(n) = F(i+j) = F(i+k**2)

[download]
which we can compute using the first formula above and 
F(k**2) = (F(k-1)+F(k+1))*F(k*(k-1)) 
          - ((-1)**k)*F(k*(k-2))

[download]
It remains to be seen whether all of this extra work buys anything.

-QM
--
Quantum Mechanics: The dreams stuff is made of

Replies are listed 'Best First'.
Re^7: OT: Finding Factor Closest To Square Root
by BrowserUk (Patriarch) on Feb 22, 2005 at 01:31 UTC

    If you haven't already installed Math::Pari for doing your factorisation, do so now. I knew it would be quicker than Math::Big, but you have to see for yourself how much faster it is to believe it. It's not just the C -v- Perl difference, it has a batch of extremely clever algorithms in there, and intelligently chooses the most appropriate one.

    The only bug-bear I have with Math::Pari so far, is the lack of a (as far as I can see), function for flattening its two dimensional vectors. The results from factorint() come back as an AoA, where the first nested array conatins the factors, and the second contains the counts, which makes them a tad awkward to maniulate.

    Examine what is said, not who speaks.
    Silence betokens consent.
    Love the truth but pardon error.
[reply]

      The results from factorint() come back as an AoA, where the first nested array conatins the factors, and the second contains the counts, which makes them a tad awkward to manipulate.

      That second arrayref would be a perfect list of counts to be handing to Algorithm::Loops::NestedLoops though. :)

      The obvious alternative (used by some other packages I've tried) would be to return 2250 = [ [ 2, 1 ], [ 3, 2 ], [ 5, 3 ] ] instead of [ [ 2, 3, 5 ], [ 1, 2, 3 ] ], but in general I've found the two forms equally easy to work with for most things.

      Hugo

[reply]
[d/l]
[select]
        That second arrayref would be a perfect list of counts to be handing to Algorithm::Loops::NestedLoops though. :)

        Yeah. One day soon the penny will drop for me regarding NestedLoops(). :(

        but in general I've found the two forms equally easy to work with for most things.

        Manipulating an array of pairs is easy using for, map etc. Manipulating pairs of parallel arrays is much fussier. I ended up writing a little sub to transpose them. There is probably a way using the built in matrix manipulations to do that if I could find it. Also, if I understood how to use the Pari looping constructs, there may be no need, and a performance advantage, to *not* manipulating the vectors manually in the Perl code--but that a ways up the learning curve right now.

        I'm blown away by the performance of Math::Pari. Not just the C -v- Perl thing, but it's collation of so much research into a single package. Of course, much of it is way over my head, and it is quite complex to use, especially if your trying to get the best from it.

        The documentation could do with a few clarifications. Even if simple things like the explanation of

        Note that a and b must be in R.

        where there is no 'R' mentioned anywhere else in the parameters. I assume they mean a "Real numbers" (or "drawn from the set of real numbers"), and maybe that's obvious for those who's formal math is more recent than mine--but it threw me through a loop when I first read it.

        A few working examples of using stuff like the fordiv from Perl would help. They show an example of using it in conjunction with some kind of interpreter (GP?), but as it is mentioned in the POD, I assume they be used from within Perl?

        I guess I need to seek out some non-trivial example Perl code that uses the more esoteric features.

        Examine what is said, not who speaks.
        Silence betokens consent.
        Love the truth but pardon error.
[reply]
[d/l]

In Section Seekers of Perl Wisdom