3 ms·
I wonder if comparing powers of sums would help? Suppose one of the sequences was 3, 7, 15, 30, and consider s = √[3] + √7 + √15 + √30. Then s^2 = 55 + 30 √2
by tzs 5y ago
I wonder if comparing powers of sums would help?
Suppose one of the sequences was 3, 7, 15, 30, and consider s = √[3] + √7 + √15 + √30.
Then s^2 = 55 + 30 √2 + 6 √5 + 6 √10 + 2 √21 + 2 √105 + 2 √210.
s^3 = 159 √3 + 90 √6 + 151 √7 + 90 √14 + 135 √15 + 105 √30 + 18 √35 + 18 √70.
...
s^30 = 1679613741139712617544067791402275 + 1187666266098277047375460186425450 √2 + 750901847525954802822187362608010 √5 + 530967788407084153582901906991810 √10 + 366402251460399628674629181584238 √21 + 259085516641872377051783075481000 √42 + 163913368573924563188162165414670 √105 + 115904254449237925942667189567670 √210
and so on.
For any given finite sequence of positive integers there is a finite set of square roots of positive integers such that all positive integer powers of the sum of the square roots of the sequence members can be expressed as a linear combination of that finite square root set with non-negative integer coefficients.
With s^n if we approximate each of the square roots by first the nearest integer not larger than the square root, and second by the nearest integer not smaller than the square root, we get a lower bound and upper bound for s^n.
Suppose we do that for the sums of the square roots of the two sequences we want to compare. For each power n, that gives us two integer ranges we can compare. If they do not overlap, we can tell which square root sum is lower.
If they do overlap, we can try a higher power n, so we can try a better square root approximation than nearest integer to get narrow ranges for the n'th powers.
What I'm hoping for is that by going to higher powers we can avoid having to do high precision square root calculations, so it can be done with just large integer arithmetic and regular floating point.
- cperciva 5y agoDoesn't help, because if you start with the sum of N square roots you end up (in the general case) with 2^N square roots once you raise it to a power.
- chrisshroba 5y agoI was curious how this would play out and didn't see your comment, so I made a Jupyter notebook of raising various sums of square roots to various powers. Posting in case anyone else finds it interesting: https://gist.github.com/chrisshroba/8f12757ecbcdd394ceccb3e9577f7c0d https://gist.github.com/chrisshroba/8f12757ecbcdd394ceccb3e9...
- readams 5y agoIf you can immediately come up with an algorithm for a well-studied computer science problem, then it's very likely the approach isn't going to work out. Notably in your case you've just converted high-precision floating point into even-higher-precision integer math. So the problem here that's inherent, which it that you might have to look at a very large number of bits of precision to find the differences, hasn't been sidestepped.
- yccs27 5y agoI guess you’re right in your first sentence, but it often helps to study some (semi-)obvious algorithms and analyze why that approach won‘t work.