Advertisement
Sokolmish

Bit-magic division by 100

Aug 13th, 2020 (edited)
1,647
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.55 KB | None | 0 0
  1. // div100 a 1000000
  2. // div100 t 1000000
  3.  
  4. #include <stdlib.h>
  5. #include <stdio.h>
  6. #include <sys/time.h>
  7.  
  8. int div100(long long dividend) {
  9.     const long long divisor = 0x28f5c29;    
  10.     return ((divisor * dividend) >> 32) & 0xffffffff;
  11. }
  12.  
  13. //
  14.  
  15. unsigned long microseconds() {
  16.     struct timeval tv;
  17.     gettimeofday(&tv,NULL);
  18.     return  1000000 * tv.tv_sec + tv.tv_usec;
  19. }
  20.  
  21. void testCorrect(long long size) {
  22.     int counter = 0;
  23.         for (long long i = 0; i < size; i++) {
  24.                 int expected = i / 100;
  25.                 int value = div100(i);
  26.                 if (expected != value) {
  27.                         printf("FAILED: %lld\t/ 100 = %d\t but value is %d\n", i, expected, value);
  28.                         counter++;
  29.                 }
  30.         }
  31.     if (counter == 0)
  32.         printf("Succuss\n");
  33.     else
  34.         printf("Failed %d times\n", counter);
  35. }
  36.  
  37. void testTime(long long size) {
  38.     unsigned long last, cur;
  39.  
  40.     last = microseconds();
  41.     for (long long i = 0; i < size; i++) {
  42.     int value = div100(i);
  43.     }
  44.  
  45.     cur = microseconds();
  46.     printf("Standart division: %ldµs\n", cur - last);
  47.  
  48.     last = microseconds();
  49.     for (long long i = 0; i < size; i++) {
  50.         int value = i / 100;
  51.     }
  52.  
  53.     cur = microseconds();
  54.     printf("Bit-magic division: %ldµs\n", cur - last);
  55. }
  56.  
  57. int main(int argc, char **argv) {
  58.     if (*argv[1] == 'a') { // Check results
  59.         long long size = atoll(argv[2]);
  60.         printf("Test correct: %lld\n", size);
  61.         testCorrect(size);
  62.     }
  63.     else if (*argv[1] == 't') { // Check time
  64.         long long size = atoll(argv[2]);
  65.         printf("Test time: %lld\n", size);
  66.         testTime(size);
  67.     }
  68.     else {
  69.         printf("Unknown option: %c", *argv[1]);
  70.     }
  71.     return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement