4 ms·

I had a similar experience in a problem in which I was requested to extract the digits of an integer before performing some other task. I proposed doing this by

I had a similar experience in a problem in which I was requested to extract the digits of an integer before performing some other task. I proposed doing this by converting it to a string and extracting the digits from the string, and that was rejected arbitrarily even though it solved the problem at hand just fine. So I spent entirely too much time during that session recreating an algorithm to extract digits via repeated division/modulo operations that would likely be much slower in practice.

tylerhou 5y ago
> repeated division/modulo operations that would likely be much slower in practice. … but that’s exactly how conversion to string works, so handrolling an algorithm would likely be around the same speed. I don’t know enough about the question, but it’s possible that the interviewer wanted to test this specifically. I’ve had interview questions which were literally “implement itoa.” In this case where itoa was part of a larger question, if I was conducting the interview I would let you convert to string for now so you could continue, but I would let you know that I wanted to revisit the digit conversion later.
- kongin 5y ago
  >… but that’s exactly how conversion to string works, so handrolling an algorithm would likely be around the same speed. https://github.com/lattera/glibc/blob/master/stdio-common/_itoa.c https://github.com/lattera/glibc/blob/master/stdio-common/_i... It's all bit-shifts, bit-masks and a lot of other hacks to get the maximum performance out of the system you're compiling the code on. Could I write something with better performance on my system? Yeah, after a week to run tests and write esoteric macros.
  - adwn 5y ago
    An optimizing compiler will turn div-by-constant and mod-by-constant into multiplications and bitshifts. For example, the Rust compiler: https://play.rust-lang.org/?version=stable&mode=release&edition=2018&gist=6ff274d702aec5de7078dba9300c9ac4 https://play.rust-lang.org/?version=stable&mode=release&edit... (select "Show assembly" on the top-left button). pub fn divmod10(x: u32) -> (u32, u32) { (x / 10, x % 10) } generates mov ecx, edi mov eax, 3435973837 imul rax, rcx shr rax, 35 lea ecx, [rax + rax] lea ecx, [rcx + 4\*rcx] sub edi, ecx mov edx, edi ret
    - kongin 5y ago
      It's still not as efficient since you're breaking on base 10 digit boundaries, not base 2, the most efficient encoding will be base 3, but alas we don't have ternary computers.
      - adwn 5y ago
        But it's a much more compact than that glibc monstrosity is. Sure, the glibc version will win in a micro-benchmark, but micro-benchmarks don't capture the effect on the instruction cache.
        kongin 5y ago
        https://en.wikipedia.org/wiki/Radix_economy https://en.wikipedia.org/wiki/Radix_economy Using a decimal expansion adds 25% overhead from pure maths. Your cache will be larger if you're working in base ten regardless of what optimizations your compiler does.
deleted 5y ago
[deleted]

tylerhou 5y ago

> repeated division/modulo operations that would likely be much slower in practice. … but that’s exactly how conversion to string works, so handrolling an algorithm would likely be around the same speed. I don’t know enough about the question, but it’s possible that the interviewer wanted to test this specifically. I’ve had interview questions which were literally “implement itoa.” In this case where itoa was part of a larger question, if I was conducting the interview I would let you convert to string for now so you could continue, but I would let you know that I wanted to revisit the digit conversion later.

kongin 5y ago
>… but that’s exactly how conversion to string works, so handrolling an algorithm would likely be around the same speed. https://github.com/lattera/glibc/blob/master/stdio-common/_itoa.c https://github.com/lattera/glibc/blob/master/stdio-common/_i... It's all bit-shifts, bit-masks and a lot of other hacks to get the maximum performance out of the system you're compiling the code on. Could I write something with better performance on my system? Yeah, after a week to run tests and write esoteric macros.
- adwn 5y ago
  An optimizing compiler will turn div-by-constant and mod-by-constant into multiplications and bitshifts. For example, the Rust compiler: https://play.rust-lang.org/?version=stable&mode=release&edition=2018&gist=6ff274d702aec5de7078dba9300c9ac4 https://play.rust-lang.org/?version=stable&mode=release&edit... (select "Show assembly" on the top-left button). pub fn divmod10(x: u32) -> (u32, u32) { (x / 10, x % 10) } generates mov ecx, edi mov eax, 3435973837 imul rax, rcx shr rax, 35 lea ecx, [rax + rax] lea ecx, [rcx + 4\*rcx] sub edi, ecx mov edx, edi ret
  - kongin 5y ago
    It's still not as efficient since you're breaking on base 10 digit boundaries, not base 2, the most efficient encoding will be base 3, but alas we don't have ternary computers.
    - adwn 5y ago
      But it's a much more compact than that glibc monstrosity is. Sure, the glibc version will win in a micro-benchmark, but micro-benchmarks don't capture the effect on the instruction cache.
      - kongin 5y ago
        https://en.wikipedia.org/wiki/Radix_economy https://en.wikipedia.org/wiki/Radix_economy Using a decimal expansion adds 25% overhead from pure maths. Your cache will be larger if you're working in base ten regardless of what optimizations your compiler does.

deleted 5y ago

[deleted]