New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Investigate whether $rat**$huge-power can be optimized with math smarts #1955

Closed
zoffixznet opened this Issue Jun 24, 2018 · 3 comments

Comments

Projects
None yet
4 participants
@zoffixznet
Contributor

zoffixznet commented Jun 24, 2018

Spotted this problem on https://www.reddit.com/r/perl6/comments/8tdfvz/handwavy_speed_test/

You can make this code a zillion times faster by just adding two characters:

# 1m46.017s
dd (1 + (.2801 / $_)) ** $_ with 100_000;

# 0.3s, where 0.1s is startup
dd (1 + (.2801e0 / $_)) ** $_ with 100_000;

And the reason is the power op on rationals first raises both numerator and denominator to the given power and then reduces them, so we end up with two huge Ints, which we probably still reduce to a Num in the end.


I figure, there are probably some mathematical tricks that can be used to optimize this in two ways:

  1. Some math to [partially] reduce the fractions without having to compute huge Ints first
  2. Fast way to determine if we're going to end up with a Num result after reduction and perhaps Numify first.
@colomon

This comment has been minimized.

Show comment
Hide comment
@colomon

colomon Jun 24, 2018

Contributor

#1 Cannot work, can it? If the Rat starts reduced (which is supposed to be the new standard, right?), then the numerator and the denominator cannot have prime factors in common. So no matter how many times you raise them to a power, you will not suddenly develop new prime factors in common.

#2 Though I guess that means you can figure out whether it's going to convert to a Num by checking if the denominator raised to the power is bigger than fits in a Rat denominator. I don't see any reason why you cannot estimate that using Nums, which should be very fast.

Contributor

colomon commented Jun 24, 2018

#1 Cannot work, can it? If the Rat starts reduced (which is supposed to be the new standard, right?), then the numerator and the denominator cannot have prime factors in common. So no matter how many times you raise them to a power, you will not suddenly develop new prime factors in common.

#2 Though I guess that means you can figure out whether it's going to convert to a Num by checking if the denominator raised to the power is bigger than fits in a Rat denominator. I don't see any reason why you cannot estimate that using Nums, which should be very fast.

@zoffixznet

This comment has been minimized.

Show comment
Hide comment
@zoffixznet

zoffixznet Jun 24, 2018

Contributor

#1 Cannot work, can it? If the Rat starts reduced (which is supposed to be the new standard, right?), then the numerator and the denominator cannot have prime factors in common. So no matter how many times you raise them to a power, you will not suddenly develop new prime factors in common.

Ah, too bad. Yes, while unmerged yet, the always-reduced is the new standard.

#2 Though I guess that means you can figure out whether it's going to convert to a Num by checking if the denominator raised to the power is bigger than fits in a Rat denominator. I don't see any reason why you cannot estimate that using Nums, which should be very fast.

At least knowing that the resultant Rat won't be reduceable should make this part fairly easy. Gonna give it a go as part of the Grant work.

Contributor

zoffixznet commented Jun 24, 2018

#1 Cannot work, can it? If the Rat starts reduced (which is supposed to be the new standard, right?), then the numerator and the denominator cannot have prime factors in common. So no matter how many times you raise them to a power, you will not suddenly develop new prime factors in common.

Ah, too bad. Yes, while unmerged yet, the always-reduced is the new standard.

#2 Though I guess that means you can figure out whether it's going to convert to a Num by checking if the denominator raised to the power is bigger than fits in a Rat denominator. I don't see any reason why you cannot estimate that using Nums, which should be very fast.

At least knowing that the resultant Rat won't be reduceable should make this part fairly easy. Gonna give it a go as part of the Grant work.

@niner

This comment has been minimized.

Show comment
Hide comment
@niner

niner Jun 24, 2018

Contributor
Contributor

niner commented Jun 24, 2018

@zoffixznet zoffixznet removed the CaR Grant label Jul 28, 2018

@zoffixznet zoffixznet removed their assignment Jul 28, 2018

@AlexDaniel AlexDaniel added the perf label Jul 31, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment