0

I need to calculate floor(log2(n)), where n is positive integer of up to 64 bits.

The value floor(log2(n)) is equal to the bit-length of n minus 1, hence the title.

I have implemented the following function:

uint8_t floorLog2(uint64_t n)
{
    uint8_t res = 0;

    uint64_t ONE = 1;
    for (uint8_t k = 32; k > 0; k >>= 1)
    {
        if (n >= (ONE << k))
        {
            n >>= k;
            res |= k;
        }
    }

    return res;
}

It works great, but...

I've realized that for 6-bit numbers, it is less efficient than the straightforward method:

uint8_t floorLog2(uint64_t n)
{
    uint8_t res = 0;

    while (n > 1)
    {
        n >>= 1;
        res += 1;
    }

    return res;
}

So I've created a combined version:

uint8_t floorLog2(uint64_t n)
{
    uint8_t res = 0;

    if (n < 64)
    {
        while (n > 1)
        {
            n >>= 1;
            res += 1;
        }
    }
    else
    {
        uint64_t ONE = 1;
        for (uint8_t k = 32; k > 0; k >>= 1)
        {
            if (n >= (ONE << k))
            {
                n >>= k;
                res |= k;
            }
        }
    }

    return res;
}

But I don't really like the branch (if/else) here.

Since I call this function many times, it impacts the overall performance of my program.

Is there a better approach that I am missing here?

halfer
  • 19,824
  • 17
  • 99
  • 186
goodvibration
  • 5,980
  • 4
  • 28
  • 61
  • Any idea except for lookup tables (arrays) please. – goodvibration Jul 30 '17 at 09:22
  • 3
    "count leading zeros" and you'll find many duplicates. – Marc Glisse Jul 30 '17 at 09:22
  • 3
    This is the kind of thing that is best done in hardware. How is your `uint256_t` defined? Is it a native type of some CPU or it is implemented using multiple smaller native integers? What CPU are you using? Does this need to be portable? – Matteo Italia Jul 30 '17 at 09:23
  • @MatteoItalia: Yes, it needs to follow the language standard and be portable to any HW. The `uint256_t` is a native type on my compiler. – goodvibration Jul 30 '17 at 09:25
  • @MarcGlisse: Can you please rephrase that in plain English? – goodvibration Jul 30 '17 at 09:25
  • 3
    "needs to follow the language standard" and "The `uint256_t` is a native type" kind of contradict each other. – chtz Jul 30 '17 at 09:27
  • @chtz: Yes, I agree. So imagine a "parallel" language which is defined exactly the same, but has an additional `uint256_t` type which "acts" the same as all other types. – goodvibration Jul 30 '17 at 09:28
  • 1
    Wouldn't a straight forward approach to `floor(log2(n))` be `floor(log2(n))`? –  Jul 30 '17 at 09:36
  • @manni66: No. If you pass `(1<<63)`, for example, it will take 63 iterations rather than 6. – goodvibration Jul 30 '17 at 09:38
  • @goodvibration Only if you believe that `log2()` requires 63 iterations. Do you have some reason for that supposition? – user207421 Jul 30 '17 at 09:52
  • What is the distribution of your numbers? What's the reason that you don't like if/else here? Why do you handle numbers less than 64 special? You could do the same with numbers where only the 6 highest bit is on, like `if (!(n<<64)) { }`. This question seems like that you've actually written no code, just you just speak theoretically. Like the sudden change from `uint256_t` to `uint64_t`. You've failed to edit `128` to `32`, in the for loop, btw. – geza Jul 30 '17 at 09:57
  • @EJP: The straightforward approach in my question is `while (n > 0) n >>= 1;`. That will take 63 iterations if `n == 1 << 63`. – goodvibration Jul 30 '17 at 10:11
  • @geza: I have actually written the code, and it does work (I actually mentioned that in the question BTW). I will therefore ignore the other part of your comment, assuming that you haven't bothered to read the question and think about it properly (a reasonable assumption IMO, considering what you wrote). – goodvibration Jul 30 '17 at 10:14
  • 2
    Have a look at examples, starting with http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup . The code samples at this link all assume a 32-bit unsigned, but adapting them for 64-bit unsigned should be straight-forward in most cases. – Peter Jul 30 '17 at 10:21
  • @Peter: I see "lookup" there, I hope it's not using arrays, but I will have a look. Thank you. – goodvibration Jul 30 '17 at 10:23
  • @goodvibration: your combined version doesn't work correctly, as I've said. My questions are adequate in this situation, but feel free to not answer them. But you cannot get the best answer for your question then. – geza Jul 30 '17 at 10:24
  • @goodvibration: I'll ask here too (like in your previous question), why can't you use arrays? What's the problem with them? – geza Jul 30 '17 at 10:24
  • @geza: Should be `while (n > 1)` up there, I will fix... – goodvibration Jul 30 '17 at 10:24
  • @geza: In the platform I am running on, array-access operations are expensive in particular. – goodvibration Jul 30 '17 at 10:25
  • @goodvibration - there are a few different approaches there, not all of them involve a lookup table. I wouldn't avoid any solution unless you've tested it on your system to see if it meets requirements. – Peter Jul 30 '17 at 10:25
  • @goodvibration: which platform is it? – geza Jul 30 '17 at 10:26
  • @geza: Ethereum Virtual Machine. – goodvibration Jul 30 '17 at 10:26
  • 1
    @goodvibration: that would help a **lot**, if you mentioned this information in your question. – geza Jul 30 '17 at 10:27
  • @geza: No one here knows it, how exactly would it help??? (I also wanted to keep the question platform-agnostic). – goodvibration Jul 30 '17 at 10:30
  • 1
    Possible duplicate of [Fast computing of log2 for 64-bit integers](https://stackoverflow.com/questions/11376288/fast-computing-of-log2-for-64-bit-integers) – Sven Marnach Jul 30 '17 at 10:39
  • 1
    because we know the platform you're optimizing for. It is not a negligible information. Even if you think that no-one knows EVM here. It helps to understand, why the limits are there. And even, one could google for EVM... btw, I meant that you should replace 128 to 32 in the for loop. That's made me think that you actually never tried this code, because it has a serious bug. – geza Jul 30 '17 at 10:39
  • @geza: I'm sorry, but I did replace that `128` with a `32` when I moved from `uint256_t` to `uint64_t`. – goodvibration Jul 30 '17 at 10:49
  • please, look at the last code snippet. There's a 128 there. – geza Jul 30 '17 at 11:02
  • @goodvibration: btw, it there any doc/blog/whatever about array access in EVM? How slow is it? Why is it slow? I'm asking this, because in your other question, there's a massive speedup in current CPU's for using arrays. Is array access that slow in EVM, that even a 20x speedup cannot counterweight it? – geza Jul 30 '17 at 11:15
  • @geza: Oh, yeah, the combined function. Thank you. – goodvibration Jul 30 '17 at 11:37
  • That's not what I asked. I asked why you thought `log2()` would take 63 operations. It doesn't, unless you hand-code it yourself as you have. The question remains why `floor(log2(n))` isn't already the right answer. – user207421 Jul 31 '17 at 01:42
  • @EJP: For a number of 64 bits, the number of iterations is 6 (using binary-search or similar). However, for input numbers smaller than 2^6, we can do it in less (aka "straightforward method" in my question). – goodvibration Jul 31 '17 at 08:34
  • @goodvibration The number of iterations of `log2()` is unknown to you. It uses a single FPU instruction, in all probability. I am not referring to the code you wrote, I am referring to @manni66's question about `floor(log2(n))`, which you still have not answered. – user207421 Aug 02 '17 at 00:50

1 Answers1

0
uint8_t floorLog2(uint64_t n)
{
    uint8_t res = 0;
    static const uint64_t ONE = 1;
    for (uint8_t k = 128; n >= 64; k >>= 1)
    {
        if (n >= (ONE << k))
        {
            n >>= k;
            res |= k;
        }
    }
    while (n > 1)
    {
        n >>= 1;
        res += 1;
    }
    return res;
}
user31264
  • 6,557
  • 3
  • 26
  • 40