What’s the fastest way to divide an integer by 3?

by

The guy who said “leave it to the compiler” was right, but I don’t have the “reputation” to mod him up or comment. I asked gcc to compile int test(int a) { return a / 3; } for an ix86 and then disassembled the output. Just for academic interest, what it’s doing is roughly multiplying by 0x55555556 and then taking the top 32 bits of the 64 bit result of that. You can demonstrate this to yourself with eg:

$ ruby -e 'puts(60000 * 0x55555556 >> 32)'
20000
$ ruby -e 'puts(72 * 0x55555556 >> 32)'
24
$

The wikipedia page on Montgomery division is hard to read but fortunately the compiler guys have done it so you don’t have to.

More Related Contents:

  1. What Every Programmer Should Know About Memory?
  2. What do the terms “CPU bound” and “I/O bound” mean?
  3. Position of least significant bit that is set
  4. How can I multiply and divide using only bit shifting and adding?
  5. How do you test running time of VBA code?
  6. Is shifting bits faster than multiplying and dividing in Java? .NET? [closed]
  7. Rounding up to next power of 2
  8. SIMD instructions lowering CPU frequency
  9. How much of ‘What Every Programmer Should Know About Memory’ is still valid?
  10. What is copy-on-write?
  11. Division without using ‘/’
  12. How can I rank observations in-group faster?
  13. Time complexity of memory allocation
  14. Deflate compression browser compatibility and advantages over GZIP
  15. Can compiler optimization introduce bugs?
  16. Why does the Java API use int instead of short or byte?
  17. RDTSCP in NASM always returns the same value (timing a single instruction)
  18. Which is better option to use for dividing an integer number by 2?
  19. Hyperparameter optimization for Deep Learning Structures using Bayesian Optimization
  20. How to do batching without UBOs?
  21. What is Big O notation? Do you use it? [duplicate]
  22. Can I use the “null pointer optimization” for my own non-pointer types?
  23. Speed up bitstring/bit operations in Python?
  24. Logger slf4j advantages of formatting with {} instead of string concatenation
  25. What branch misprediction does the Branch Target Buffer detect?
  26. Fast multiplication/division by 2 for floats and doubles (C/C++)
  27. Can I efficiently return an object by value in Rust?
  28. Branchless code that maps zero, negative, and positive to 0, 1, 2
  29. Fastest way to loop through a 2d array?
  30. 64/32-bit division on a processor with 32/16-bit division

Leave a Comment