DEV Community

Discussion on: Daily Challenge #257 - Halving Sum

Collapse
 
qm3ster profile image
Mihail Malo • Edited

I like the word problem in the question, where decimals are mentioned, but not the example.
So the examples would be:

  • 25 => 25 + 12.5 = 25
  • 28 => 28 + 14 + 7 + 3.5 = 49
const half = n => n % 2 ? n : n + half(n / 2) // ew, not even tail recursion

1) However, we know that the infinite series n + n/2 + n/4 + n/8 + ... converges to 2n.
(because it is 2n * (1/2 + 1/4 + 1/8 + 1/16 + ⋯) link)
2) And we know that the highest power of 2 we can cleanly divide a number is the number of trailing zeros it has:

0b1100 / 2 = 0b110
0b110 / 2 = 0b11
0b11 / 2 = 'loss.jpg'

3) And we also know that the sum of the infinitely many items we don't get to add looks like, for example n/8 + n/16 + n/32 + ..., which is equivalent to 2n/8* (1/2 + 1/4 + 1/8 + 1/16 + ⋯) (and converges to (2n/8)).
4) So the sum without that tail is 2n - 2n/8, where 8 is 2 to the power of number of trailing zeros of n.
5) Well, turns out there is an intrinsic for trailing zeros.

Rust

fn half(x: u64) -> u64 {
    let highest = x.trailing_zeros();
    2 * x - (x >> highest)
}

which results in just this assembly

example::half:
        test    rdi, rdi
        je      .LBB0_1
        bsf     rcx, rdi
        jmp     .LBB0_3
.LBB0_1:
        mov     ecx, 64
.LBB0_3:
        mov     rdx, rdi
        shr     rdx, cl
        lea     rax, [rdi + rdi]
        sub     rax, rdx
        ret

Is that good, one might ask? No idea, IDK how to computers.