in reply to Re: Finding divisors from factors
in thread Finding divisors from factors

Thanks Rolf.

The powerset solution was mainly to point out this simple way. It does work -- one just needs to remove duplicates using a hash.

It looks like your solution is very similar to my followup, we just do the multiply through a little different. The time is pretty close, and both faster than my earlier solutions.

They also have the advantage of not doing excess computation, which is important when we move to bigints where every operation is expensive (with Math::BigInt at least).

Replies are listed 'Best First'.
Re^3: Finding divisors from factors (updated)
by LanX (Saint) on Oct 09, 2014 at 09:19 UTC
    Of course you can still speed up this solution, but I doubt it would be more than micro optimizations or just related to Perl specific features/bottlenecks (like overhead for allocating temporary arrays) °

    This needs only one multiplication per divisor, hence its O(#D) i.e. <= O(2^#P) for worst case, that's pretty optimal.

    But I like the simplicity and readability compared to other suggestions, so personally I wouldn't start micro optimization now just to save 10 or 20 %.

    update
    Of course I'm not comparing to solutions using XS modules. In that case just use C directly.

    Cheers Rolf

    (addicted to the Perl Programming Language and ☆☆☆☆ :)

    °) or moving data or linearizing loops

    update

    E.G. you could try to replace the maps with direct

    push @D_new, ($_*$p) for @D

    expressions!

    This could should be faster... but I'm not very motivated to benchmark myself. :)

[reply]
[d/l]

In Section Seekers of Perl Wisdom