9 ms·
The Lost Art of Logarithms
- tombert 2y agoI started using LMAX Disruptor for some projects. One quirk with Disruptor is that the queue size always has to be an exponent of two. I wanted to make sure that I always have at least enough room for any size and I didn't want to manually compute, so I wrote this: var actualSize = Double.valueOf(Math.pow(2, Math.ceil(Math.log(approxSize) / Math.log(2)))).intValue(); A bit much for a single line, but just using some basic log rules in order to the correct exponent. I learned all this in high school, but some of my coworkers thought I was using this amazing, arcane bit of math that had never been seen before. I guess they never use log outside of Big-O notation.
- mananaysiempre 2y agoThis is perfectly usable, of course, but I’d write var actualSize = Integer.highestOneBit(approxSize - 1) << 1; purely to avoid involving the horrors that live beneath the humble pow() and log(). (Integer.highestOneBit, also known as “isolate leftmost bit”, “most significant one”, or the like, essentially has to be a primitive to be efficient, unlike its counterpart for the lowest bit, x&-x. The actual CPU instruction is usually closer to Integer.numberOfLeadingZeros, but that’s just a bitshift away.)
- tombert 2y agoThat's pretty cool; I didn't even consider doing any cool bitwise arithmetic. I didn't particularly care about performance or anything for this particular case, since it runs exactly once at the start of the app just to initiate the Disruptor.
- markrages 2y agoshouldn't it be var actualSize = 1 << Integer.highestOneBit(approxSize - 1); ?
- mananaysiempre 2y agoNope. I don’t know why the Java folks decided not to use the fairly standard verb “isolate” for this method, but that’s what it is[1]: > public static int highestOneBit(int i) > Returns an int value with at most a single one-bit, in the position of the highest-order ("leftmost") one-bit in the specified int value. Returns zero if the specified value has no one-bits in its two's complement binary representation, that is, if it is equal to zero. There isn’t a straight floor(log2(·)) as far as I can tell, only Integer.numberOfLeadingZeros, and turning the former into the latter is annoying enough[2] that I wouldn’t prefer it here. [1] https://docs.oracle.com/javase/8/docs/api/java/lang/Integer.html#highestOneBit-int- https://docs.oracle.com/javase/8/docs/api/java/lang/Integer.... [2] https://docs.oracle.com/javase/8/docs/api/java/lang/Integer.html#numberOfLeadingZeros-int- https://docs.oracle.com/javase/8/docs/api/java/lang/Integer....
- markrages 2y agoThanks. What a weird API.
- layer8 2y agoThe above gives an incorrect result for approxSize = 1 (namely 0). The following works (for values up to 2^30, of course): var actualSize = Integer.MIN_VALUE >>> Integer.numberOfLeadingZeros(approxSize - 1) - 1; Or, if you want 0 to map to 0 instead of to 1: var actualSize = Integer.signum(approxSize) * Integer.MIN_VALUE >>> Integer.numberOfLeadingZeros(approxSize - 1) - 1; Of course, you could also use a variation of: var actualSize = Math.min(1, Math.Integer.highestOneBit(approxSize - 1) << 1);
- ajsnigrutin 2y agoJust shift the size to the right 1 bit and count the shifts until the value turns to zero, and you'll get your number 2 exponent for the size :)
- kenjackson 2y agoNotation for writing log has always bugged me. Like I feel like it should be more like <10>^<527> which would be the log base 10 of 527. That's not it, but something. The current notation just doesn't feel quite right.
- Jtsummers 2y agohttps://mathcenter.oxford.emory.edu/site/math108/logs/ https://mathcenter.oxford.emory.edu/site/math108/logs/ Some people have suggested the "triangle of power".
- awesome_dude 2y agoThe Triangle of power explanation of logarithms is what really got me across logs. It wasn't until seeing the triangle and having the relationships explained that I had any clue about logarithms, up until then logs had been some archaic number that meant nothing to me. Because of the triangle of power, I now rock up to B and B+ Trees and calculate the number of disc accesses each will require in the worst case, depending on the number of values in each block (eg, log2(n), log50(n) and log100(n))
- cafeinux 2y agoIronically, that notation, which I just discovered, confuses me more than anything else. Logs clicked for me when someone online said "amongst all the definitions we have for logs, the most useful and less taught is that log() is just a power". At that exact instant, it's like if years of arcane and foreign language just disappeared in front of my eyes to leave only obviousness and poetry.
- awesome_dude 2y agoThat is not without humour :) I don't understand the comment about it just being a power, but, for me, knowing that it's filling in the third vertice on the triangle with exponents at the top, and n on the other is what makes it work for me - I now know in my head when I am looking for the log of n, I am looking for the exponent that would turn the log into n. I don't go looking for the exact log, I only look for whole numbers when I am calculating the value in my mind. But it makes sense when I am looking for the log2 of 8 to know that the answer is "what exponent will make 2 into 8"? and that's "3"
- Animats 2y agoIs this the same author who wrote Win32 API books?
- Jtsummers 2y agoYes. https://www.lostartoflogarithms.com/author/ https://www.lostartoflogarithms.com/author/
- fph 2y agohttps://www.charlespetzold.com/PetzoldTattoo.jpg https://www.charlespetzold.com/PetzoldTattoo.jpg
- ohgr 2y agoYes the office door stop as it was known as at our place. Top book though just faded in utility and no one had the heart to dispose of it because of the good memories.
- Dwedit 2y agoGood book indeed, just that I wouldn't use a book to look up Win32 API functions.
- hyperopt 2y agoCharles Petzold wrote one of my favorite books - "Code: The Hidden Language of Computer Hardware and Software". Very excited to see how this turns out and thanks for giving some of this knowledge away for free!
- tocs3 2y agoI would also recommend the "NAND to Tetris" book. Covers much the same ground (as I remember things anyway) but is a hands on approach. I enjoyed Code also though and is worth a look for those interested.
- deleted 2y ago[deleted]
- tmoertel 2y agoHere's an logarithmic fact that I've made use of frequently: If X is a random variable having a uniform distribution between zero and one, then –ln(X)/λ has an exponential distribution with rate λ. This relationship comes in handy when, for example, you want to draw weighted random samples. Or generating event times for simulations.
- zwnow 2y agoHow long do I have to study math to understand this?
- whereismyacc 2y agoto understand what they said, or to understand a proof of why it would be true? any stats class would be enough to understand what they said
- pc86 2y agoI know what all these words mean, it "makes sense" to me in the sense that I read it and I think "ok.." but I wouldn't have the slightest idea how to use this to get weighted random samples or "generate event times." So I guess I "understand it" in the sense that it doesn't sound like a foreign language, but I can't apply it in any meaningful way.
- pvg 2y agoDepends where you're starting from but from highschoolish maths you can probably sort this out in a few hours or days.
- bgnn 2y agoDepends on how much you practiced high school math. It's not hard but we forget it without practice.
- deleted 2y ago[deleted]
- jrussino 2y ago
- inasio 2y agoThere used to be practical value to be able to do some basic back of the envelope log calculations in your head (no calculators, this was how you did fast multiplications/divisions or exponents). There's a story in Feyman's Surely you're joking book about Los Alamos scientists doing speed competitions for mental log calculations
- NoMoreNicksLeft 2y agoIf the author is in here, thank you. Been looking for a text for my daughter on the subject. This might just fit the bill. If you're just the linker, then thank you Ozanonay.
- inasio 2y ago(I'm sure this is in the book) John Napier, the father of logarithms (the N in ln), basically had a sweatshop of human calculators making log tables over something like 20 years - critical for celestial navigation. There was a huge price attached to the person that developed a method to safely navigate across the oceans, also lead to the invention of the pocket watch
- dekhn 2y agoI learned the multiplication using addition and a lookup table in a class taught by Huffman (of Huffman compression fame). You weren't allowed to use a calculator on the test. But my absolute favorite trick is base conversions, https://www.khanacademy.org/math/algebra2/x2ec2f6f830c9fb89:logs/x2ec2f6f830c9fb89:change-of-base/a/logarithm-change-of-base-rule-intro https://www.khanacademy.org/math/algebra2/x2ec2f6f830c9fb89:... with some practice you can do approximate base conversions (power to 2 to power of 10 or e) in your head
- dkislyuk 2y agoI found that looking at the original motivation of logarithms has been more elucidating than the way the topic is presented in grade-school. Thinking through the functional form that can solve the multiplication problem that Napier was facing (how to simplify multiplying large astronomical observations), f(ab) = f(a) + f(b), and why that leads to a unique family of functions, resonates a lot better with me for why logarithms show up everywhere. This is in contrast to teaching them as the inverse of the exponential function, which was not how the concept was discussed until Euler. In fact, I think learning about mathematics in this way is more fun — what original problem was the author trying to solve, and what tools were available to them at the time?
- cauliflower2718 2y agoThis follows directly from the fact that exp(x+y)=exp(x)exp(y).
- dkislyuk 2y agoYes, but such a property was not available to Napier, and from a teaching perspective, it requires understanding exponentials and their characterizations first. Starting from the original problem of how to simplify large multiplications seems like a more grounded way to introduce the concept.
- kccqzy 2y agoFrom a teaching perspective it goes like this: first we learn additions, and to undo additions we have subtractions; then we learn repeated additions i.e. multiplications, and to undo multiplications we have divisions; finally we learn repeated multiplications, i.e. exponentiation, and to undo exponentiation we have logarithms and roots.
- BobaFloutist 2y agoYou see how one of those isn't like the others?
- adornKey 2y agoThe Logarithmic derivative is also something that is surprisingly fundamental. (ln(f))' = f'/f In function theory you use it all the time. But people rarely notice, that it related to a logarithm. Also the functions that have nice logarithmic derivative are a lot more interesting than expected. Nature is full of Gompertz functions. Once you're familiar with it, you see it everywhere.
- sva_ 2y ago> Charles Petzold Haven't heard that name in a while. For me he's the WinApi guy - learned a lot from him when I first started programming.
- mixmastamyk 2y agoStill can! His classic book Code is fantastic and has a recent second addition.
- jrmg 2y agoCode is a masterpiece. Anyone here who hasn’t read it should do so - you might think it’s ’below you’, but it’s so well written it’s a joy to read, and I suspect you’ll come out thinking of some things differently. It reminded me why I love computing.
- mixmastamyk 2y ago^edition.
- esafak 2y agoPC Magazine contributor, for me.
- deleted 2y ago[deleted]
- deleted 2y ago[deleted]
- hughw 2y agoI feel frustrated that we cannot conceive of numbers like 10^80 (atoms in the universe) or 10^4000 (number configurations for a system with 4000 variables having 10 states each). Maybe there are superbrains out there in the universe that can do so.
- crazygringo 2y agoI guess you have to define what you mean by "conceive". I'm not sure you can even conceive a number like 1,000, if you're talking about holding an intuitive visual understanding in your mind at once. Like, I can easily see 100 in my mind's eye as a 10x10 grid of circles. Even if I don't see each one clearly, I have a good sense of the 10 on each edge and the way it fills in. But ask me to imagine 10 of those side-by-side to make 1,000, and I don't think I can. Once I imagine the 10 groups, each one is just a square simplification, rather than any individual pieces within. But I'm totally familiar with 1,000 as a concept I can multiply and divide with, and I can do math with 10^80 as well. And I can do so fairly "intuitively" as well -- it's just all the numbers up to 80 digits long. Even 4,000 digits fits on a single page of a book.
- hughw 2y agoMy first cut at conceiving is to answer "how long would it take a really fast computer to count to that number". The answer for 10^4000 is still something like 10^3978 years. So, a still inconceivable time. (100 tera-ops computer) [edited to correct calculation)
- crazygringo 2y agoBut the length of time it takes a modern computer to count to 10 or 1,000 is perhaps inconceivably small by your metric, no? Your idea arbitrarily selects numbers around 2 billion as being conceivable, at least for a single core on my MacBook. But my question isn't what makes 10^4000 inconceivable -- my question is what makes 10^4000 any less conceivable than 1000. To me, they're both firmly in the realm of abstractions we can reason about using the same types of mathematical methods. They're both qualitatively different from numbers like 5 or 10 which are undoubtedly "conceivable".
- kqr 2y agoI can strongly recommend memorising some logarithms for use in mental maths. It's given me powers I did not expect to have! Here's what I wrote about it when I started: https://entropicthoughts.com/learning-some-logarithms https://entropicthoughts.com/learning-some-logarithms
- xelxebar 2y agoWhat reflections do you have putting this into action over the year since that post? BTW, your blog is one of my absolute favorites!
- kqr 2y agoIt's been about as useful as one would expect. I don't need it daily, but when I need it, I can usually estimate a good enough answer in the time it takes someone else to do it on a calculator. It has also helped a little with getting a geometric appreciation for numbers, but I suspect that could be improved significantly with more active practice.
- nakedneuron 2y agoGreat blog! Interesting fact that memory decay also is inherently logarithmic/exponential. Learning logs with SRS is so meta.
- aquafox 2y agoInteresting insight why applying a log transform often makes data normally distributed: Pretty much all laws of nature are multiplications (F=ma, PV=nRT, etc). If you start with i.i.d random variables and multiply them, you get log-normal data by virtue of the central limit theorem (because multiplications are additions on a log scale; and the CLT is also somewhat robust to non iid-ness). Thinking of data as the result of a lot of multiplications of influential factors, we thus get a log-normal distribution.
- TrainedMonkey 2y agoAll data is linear when plotted on a loglog scale with a thick marker.
- aquafox 2y agoBut in my explanation, there is no x axis.
- kqr 2y agoNo but it holds more generally. Taking the log of data tends to make it look "more correct" even when it's not theoretically justified, and this can lead to very wrong conclusions.
- genewitch 2y agoMatt Parker says it's because that's how humans are naturally inclined to think, and used the midway point between 1 and 9 to illustrate. We'd say five but "children and others not exposed to math would say 3" and then gave some explanation with beads or coins. It didn't make sense to me but I do know that if a graph is log scale I need to actually look at it harder to make sure they're not trying to pull a fast one on us here folks.
- wolfi1 2y agothe joy of an engineer is to find a straight line in a double logarithmic diagram
- BinRoo 2y agoOne of my favorite tricks in elementary school was to convince people I can calculate any logarithm for any number of their choosing. > Me: Pick any number. > Friend: Ok, 149,135,151 > Me: The log is 8.2 Of course I'm simply counting the number of digits, using 10 as the base, and guessing the last decimal point, but it certainly impressed everyone.
- ted_dunning 2y agoYou can do even better if you memorize three numbers: 301, 477, 845. These are the values of 1000log10(n) for n = 2, 3, 7. From these you can quickly get the values for 4 (= 22), 5 (=10/2), 6 (=23), 8 (=222) and 9 (=33). For your example 1.49 is close to 3 / 2 so the log will be very close 0.477 - 0.301 = 0.176. This means that your answer is near 8.176 (actual value is 8.173). This tiny table of logs can also let you answer parlor trick questions like what is the first digit of 2^1000 (the result is very nearly 10^301 but a bit above, so 1 is the leading digit).
- kqr 2y ago> 149,135,151 This is 8-point-something as you say. 1.49 is in between 1.2 and 1.6 and I have memorised log(1.2)=0.1 and log(1.6)=0.2, so I would think log(1.5) is close to 0.17, using sloppy linear interpolation. That would make log(149,135,151) approximately 8.17. My calculator also says 8.17. Your guess was good! I have found linear interpolation such an intuitive approximation method that the tradeoff of having to memorise more logarithms is worth it.
- spapas82 2y agoOne of the best uses of logarithms is how they can be used to quickly calculate db (as in decibel) gains and losses mentally. See this older comment for more details https://news.ycombinator.com/item?id=32550539 https://news.ycombinator.com/item?id=32550539
- xelxebar 2y agoHow timely! I just learned how to use a slide rule yesterday. Looking to pick one up, and a bit overwhelmed by the plethora of choices, I went down a small rabbit hole[0]. Some slide rules produced are pure works of art! Lately, I've been rediscovering the surprising niceties that analog tools can provide over our everything-is-a-panel-of-glass interfaces these days. Recently, I have been enjoying pen and paper as my editor for initial drafts of projects I'm coding. Does HN have love for any analog tools in particular? [0]:https://sliderulemuseum.com/ https://sliderulemuseum.com/
- divbzero 2y agoWhere can I get the meter-long slide rule the man is holding in OP?
- 7402 2y agoThey show up on eBay. A search this minute revealed two: https://www.ebay.com/itm/205220626817 https://www.ebay.com/itm/205220626817 https://www.ebay.com/itm/156686655356 https://www.ebay.com/itm/156686655356 They go for a bit more than the original price, according to this: "Pricing varied by retailer, however Pickett did offer demonstration slide rules in 4 foot and 7 foot lengths: a 4 foot rule sold for $15 and the 7 foot rule was $25 in 1960. These were available with scales to match models N4, N803, and N1010 with the Ln scale added. These large rules were available free to schools which ordered 24 or more slide rules!" [0] https://www.sphere.bc.ca/oldsite/test/pickett.html https://www.sphere.bc.ca/oldsite/test/pickett.html
- johnm 2y agoIndeed, I use pen/pencil and (dot) paper. Different brain space.
- Rendello 2y agoI've been doing a math course and occasionally think of picking up these analogue tools. Someone on Hacker News had me interested in the Soroban, the Japanese abacus [1], which is still used to train insane mental math speeds to this day [2]. 1. https://en.wikipedia.org/wiki/Soroban https://en.wikipedia.org/wiki/Soroban 2. https://www.youtube.com/watch?v=s6OmqXCsYt8 https://www.youtube.com/watch?v=s6OmqXCsYt8
- kazinator 2y agoI recommend the classic Introduction to Logarithms, by Cormen, Rivest, Leiserson et al.
- cuttothechase 2y agoCharles Petzold was one of my favorite tech authors from the way begone era. Written in a style very similar in vein to the Lost of Art of Logarithms he made me fall in love with the various mundane tech concepts that would never jump out as a anything of interest, otherwise. What a treat!
- tiahura 2y agoProgramming Windows 95 was invaluable.
- westurner 2y agoNotes from "How should logarithms be taught?" (2021) https://news.ycombinator.com/item?id=28519356 https://news.ycombinator.com/item?id=28519356 re: logarithms in the Python standard library, NumPy, SymPy, TensorFlow, PyTorch, Wikipedia
- alanh 2y agoSo interesting! The author doesn’t, I believe, yet cover how the first log tables were computed (by hand), so I asked ChatGPT. This may be of interest: https://chatgpt.com/share/67d3a64d-f8a8-8012-bde3-e80813b2b402 https://chatgpt.com/share/67d3a64d-f8a8-8012-bde3-e80813b2b4...
- JackFr 2y agoA 300 year old log table! What an opportunity to confirm Benford’s Law! https://en.m.wikipedia.org/wiki/Benford's_law https://en.m.wikipedia.org/wiki/Benford's_law “The discovery of Benford's law goes back to 1881, when the Canadian-American astronomer Simon Newcomb noticed that in logarithm tables the earlier pages (that started with 1) were much more worn than the other pages.”
- mikewarot 2y agoThe traditional explanations of logarithms I've encountered are far too math and terminology heavy for most people to grasp. Think of a number line.... show example..... 1..2..3..4..5.. etc Any given move to the right, makes the value go up by 1. But... What if we did a special number line where each time it doubled instead of adding one? 1..2..4..8..16, etc... That line would go up way to fast to see numbers like 10, so we can expand it out a bit...show that... and start to fill in the numbers... 2^10 (1024) is almost 1000... so you can divide that distance by 3 to get 10 on the line, then move one unit left for 5... and build out a slide ruler. Computing logarithms with a 4 function calculator isn't hard by the way, I used to do it for fun on my lunch breaks.
- max_ 2y agoI wish there was a mailing list I could subscribe to so I could know when the book os complete. Or a pre-order on Amazon?
- yujzgzc 2y agoI have a few old math manuals at home, from late 19th / early 20th century. Many of them have a logarithm table as an appendix. It looked like the type of things that if you had a few extra sheets to print to make a booklet, you'd just add because it was bound to be very useful to someone.
- hansmayer 2y agoWow, I thought it was just some random guy, but was then quite surprised to see this was being authored by none other than the legendary Charles Petzold. I'd buy this book - just to put it next to my copy of "Programming Windows 95" (who remembers?) :)
- stpedgwdgfhgdd 2y agoWell written and fun to read! (For nerds)
- jamalaramala 2y agoThere was an interesting text, by Isaac Asimov, where he explained in a very clear way the historical importance of logarithms -- they allowed Kepler to finalize his work by replacing tables of multiplications (which were difficult and error-prone) with sums.
- vismit2000 2y agoRealm of Algebra by Isaac Asimov: https://archive.org/stream/RealmOfAlgebra-English-IsaacAsimov/asimov-algebra_djvu.txt https://archive.org/stream/RealmOfAlgebra-English-IsaacAsimo...
- vismit2000 2y agoLogging the World - Oliver Johnson (Oxford Mathematics): https://youtu.be/UsK52iZMsxo https://youtu.be/UsK52iZMsxo
- stephencwelch 2y agoYeah love this angle - I made a video in a similar vein: https://www.youtube.com/watch?v=OjIwCOevUew https://www.youtube.com/watch?v=OjIwCOevUew
- sali0 2y agoHuge fan of your channel! Great content.
- cytocync 2y ago[dead]
- ilija139 2y agoOff-topic, but anyone knows where to buy such [1] old but not rare (so they are cheap enough) math books? In UK and globally? Is e-bay and perhaps amazon the best place? How to avoid fakes? [1] https://www.lostartoflogarithms.com/chapter01/ https://www.lostartoflogarithms.com/chapter01/
- vanderZwan 2y agoRelated: in a reaction to a comment I wrote about logarithms about a month ago[0], saulpw recently linked his own idea of making logarithms more "accessible" to the masses by introducing magnitude-based notation: https://saul.pw/mag/ https://saul.pw/mag/ I think it is a really nice idea that should be spread more widely. It might be Pi day, and while I traditionally complain that Tau is better for contrarian reasons (hey at least I'm honest), we might as well co-opt the extra attention maths gets for other mathematical causes. [0] https://news.ycombinator.com/item?id=43036094 https://news.ycombinator.com/item?id=43036094
- Enginerrrd 2y agoFor what it's worth, I'm really not a fan. There's a reason we use scientific notation, and it's actually partly because in the era of slide-rules, it was INCREDIBLY helpful notation that makes it trivial to estimate things like order of magnitude. People performed all manner of operations and kept the magnitude part in their head. It MADE people more magnitude aware. This magnitude-only based notation is the one that's actually more needlessly complex and error prone. There's no sensible way to manage significant figures or rounding error in simple operations like addition and subtraction. And simple operations, like adding/subtracting two numbers are really non-trivial. If you have to start each operation by converting to a useful format and then converting back, what have you gained exactly by using the notation?
- anjakefala 2y agoI think the argument is that for non-scientific usecases, folks don't really need to think about error or significant digits. By focusing on the significand too much laypeople aren't grasping how large and small these numbers are relative to each other. It's not being put forward as a recommended tool for scientists when reasoning about precise values. It's put forward for laypeople when trying to understand the vastness of the universe.
- vanderZwan 2y agoYes, that was my take-away too. I suspect it's a wonderful way of teaching intuition for differences in scale, which is something that's a lot more important to us today than it was a few centuries ago. Easy mental guesstimates should not be underestimated as a valuable tool
- deleted 2y ago[deleted]
- sourtrident 2y agoFunny how logarithms shaped navigation, astronomy, and music—yet now they're mostly a forgotten button gathering dust on our calculators. Hidden tech history right there.