15

Logarithms give me a headache

Comments
  • 0
    Yeah me too
  • 4
    Easy if you had exponentials before. You take some given number to the power of shit and get a given result. What's the shit? Fuck yeah, that's the logarithm.
  • 1
    @Fast-Nop Instructions not clear. Dick stuck in shit.
  • 2
    A logarithm is “how many times can I multiply this number to get to that number”?
  • 4
    A logarithm is "how many digits are in this number", too.

    At least you can use it that way.

    Want to know how many digits are in e.g. a binary number (base2)?

    log(x)/log(2)

    What about hex (base16)?

    log(x)/log(16)
  • 5
    https://youtu.be/cEvgcoyZvB4
    3blue1brown got you covered
  • 2
    @junon I used this extensively in basic to determine number length. I didn’t have a to_string method, and log is faster anyway!
  • 2
    Logarithms turn multiplication into addition, in the same way that exponentiation turns addition into multiplication.
  • 0
    At this age, you shouldn't complain about learning basic stuff
  • 0
    trueeeeeeeeeee :(
  • 1
    Die with migrane
  • 0
    @Root is it really faster? Did you test it? It’s not obvious for me.
  • 0
    @Lensflare Implement both. Count the operations.
  • 0
    //log base 10
    function log(n){
    lg = 0
    while(n >= 10){
    lg++
    n/=10
    }
    return lg
    }
    My code, a little drunk so might be wrong whatever
  • 0
    @Root I guess counting would only work with decompiled assembly code.

    Because how many operations is log? And how many is int to string conversion?
  • 2
    @Lensflare @d-fanelli You can make a good guess with log2 in assembly (leading zero counting) and adjust with a base10 comparison to get a very accurate log10 in only a handful of instructions.

    Don’t have time to write it up in more detail right now. Sorry!

    Int to string conversion takes more clocks, and then you need to scan the resulting length, too.
  • 3
    @Lensflare @d-fanelli @Root or use the old trick that you can isolated the LSB 1 by doing n & (~n + 1) (I think, something like that, it's been a while) and then use what's effectively an assembly binary search by essentially "folding" the number in halves to find that position of that 1. This gets you the position of that 1 in a handful of assembly instructions, proportional to the log of the length of the binary number (so, very very efficient).

    A similar trick is used in Kernighan's algorithm, though without the binary search.

    If you're processing numbers in reversed bit patterns, this is equivalent to finding an approximate log2. I've actually use this trick in a hot code path both in software and in hardware (on FPGA) and it gave a pretty nice speed bump (didn't have an integer log2 instruction or hardware primitive).
Add Comment