3 ms·

I don't understand point d) What do you mean by efficient? Any other literature you could reference? Cause this sounds interesting and I'd like to do some mor

by rocqua 7y ago

I don't understand point d) What do you mean by efficient? Any other literature you could reference? Cause this sounds interesting and I'd like to do some more research into this.

lonelappde 7y ago
The cost of finding a leaf in balanced tree (with data only at leaves, which is how we represent integers in base B) of size N is on average proportional to its branching factor B multiplied by its height H. Height is (log N)/(log B), so cost is B * (log N)/(log B). By derivatives, that's minimized when B satisfies 0 = (log N) (1 / (log B) + B(-1/((log B)^2)(1/B) == 0 = 1/(log B) - 1/(log B)^2 1 = log B Base of the logarithm = B. This looks like you can pick any logarithmic base b you want, and so any B you want, but in fact the derivative I wrote assumes e is the base (hence the term "natural" logarithm. Other bases b would yield a scaling factor of ... e/b, since d(e^x)/dx = e^x and b^x = e^((ln b) x) You can chase "deeper" reasons for this all day long by digging deeper into the the many definitions/properties of e and proving they are equivalent. Playing with e is the most fun you can have in pre/calculus.
Double_Cast 7y ago
Frankly, it's just a pattern I've observed from playing with numbers myself. I'm unsure how to explain it properly, and I have no academic sources to point toward. You can probably find a better explanation somewhere in an article on optimization problems. The intuition is that (e) is the optimal water-level when limited water is distributed among a variable amount of buckets where all the filled buckets multiply each other. Alternatively, it's like how volume() is maximized where volume(x, y, z) = (x y z) const = (x + y + z) when (x = y = z). Except in our original situation, the number of dimensions is arbitrary instead of fixed.

3 ms·

I don't understand point d) What do you mean by efficient? Any other literature you could reference? Cause this sounds interesting and I'd like to do some mor

by rocqua 7y ago

I don't understand point d) What do you mean by efficient? Any other literature you could reference? Cause this sounds interesting and I'd like to do some more research into this.

lonelappde 7y ago
The cost of finding a leaf in balanced tree (with data only at leaves, which is how we represent integers in base B) of size N is on average proportional to its branching factor B multiplied by its height H. Height is (log N)/(log B), so cost is B * (log N)/(log B). By derivatives, that's minimized when B satisfies 0 = (log N) (1 / (log B) + B(-1/((log B)^2)(1/B) == 0 = 1/(log B) - 1/(log B)^2 1 = log B Base of the logarithm = B. This looks like you can pick any logarithmic base b you want, and so any B you want, but in fact the derivative I wrote assumes e is the base (hence the term "natural" logarithm. Other bases b would yield a scaling factor of ... e/b, since d(e^x)/dx = e^x and b^x = e^((ln b) x) You can chase "deeper" reasons for this all day long by digging deeper into the the many definitions/properties of e and proving they are equivalent. Playing with e is the most fun you can have in pre/calculus.
Double_Cast 7y ago
Frankly, it's just a pattern I've observed from playing with numbers myself. I'm unsure how to explain it properly, and I have no academic sources to point toward. You can probably find a better explanation somewhere in an article on optimization problems. The intuition is that (e) is the optimal water-level when limited water is distributed among a variable amount of buckets where all the filled buckets multiply each other. Alternatively, it's like how volume() is maximized where volume(x, y, z) = (x y z) const = (x + y + z) when (x = y = z). Except in our original situation, the number of dimensions is arbitrary instead of fixed.