Patashu / break_eternity.js

A Javascript numerical library to represent numbers as large as 10^^1e308 and as small as 10^-10^^1e308. Sequel to break_infinity.js, designed for incremental games.
MIT License
122 stars 46 forks source link

implement arbitrary height analytic sroot (probably through trial and error?) #8

Open Patashu opened 5 years ago

Patashu commented 5 years ago

https://en.wikipedia.org/wiki/Tetration#Inverse_operations

neither seems to have a simple recursive definition, so this is annoying :tm:.

Patashu commented 5 years ago

Oh, there's a slog approximation on its page:

https://en.wikipedia.org/wiki/Super-logarithm#Approximations

Maybe I could try it sometime.

https://en.wikipedia.org/wiki/Iterated_logarithm

'Iterated Logarithm" aka log* is almost the same too.

As for sroot, we can at least implement ssqrt if lambertw is implemented ( https://github.com/Patashu/break_eternity.js/issues/6 ) and then see where we can go from there.

http://mrob.com/pub/math/largenum-3.html has an sroot approximation which is literally 'use Newton's Method'. Maybe this is useful, maybe not?

It also has an interesting example of slog10(), which looks like it's literally the 'extract the layer, mag becomes a fractional layer' operator.

Patashu commented 5 years ago

slog implemented - and since it uses the same linear approximation as tetrate, they are truly inverses of each other!

Patashu commented 2 years ago

This is still an open issue. Now that slog uses guess-and-check to get exact values, the precedent has been set to write an sroot that accepts arbitrary arguments. Of course, there's a lot of fiddly work with edge cases, and how to find the first guess is a good question, but I think this would be good to solve.

EDIT: I think the trick is to binary search on slog representation. If you start with a good guess (and I think a good guess is 'N layers down where N is the sradical, but don't go below 1, and be very careful how far you step when you're below 1 (or some similar constant), but otherwise double until you change directions then halve after that) then I think you'll converge quickly. In the worst case you could need 1000 iterations but I think in practice this would only need 50ish, like new slog. It's likely to end up slow, but it's more important to be right than slow, especially if you give the user controls to decide how right/slow they want to be. Also, the algorithm needs to terminate when the value stops changing.

jakub791 commented 2 years ago

Isn't this just like root but you tetrate instead of exponentiate?

Patashu commented 2 years ago

Yep! Specifically if a^^b == c, then sroot_b(c) == a

jakub791 commented 2 years ago

Or is tetration to numbers below 1 but greater than 0 not implemented?

Patashu commented 2 years ago

Works great.

new Decimal(10).tetrate(0.9).toString()
'6.989961179534713'
new Decimal(10).tetrate(0.5).toString()
'2.4770056063449646'
jakub791 commented 2 years ago

Then couldn't you implement sroot like root but with tetrate instead of pow?

MathCookie17 commented 8 months ago

This issue should be closed now - I implemented linear_sroot (arbitrary-height sroot for the linear approximation) in 1.4.0, and as long as the analytic approximation isn't extended to all bases, sroot for it doesn't make sense.

Patashu commented 8 months ago

I still think that analytic arbitrary base tetration is something this library should have, but I don't anticipate it any time soon due to the high difficulty.

MathCookie17 commented 5 months ago

Changed the title, since linear sroot is implemented already.