daily pastebin goal
38%
SHARE
TWEET

Untitled

a guest Aug 10th, 2018 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. binary roots of an integer
  2. N is an integer within the range [1..2,147,483,647].   For example, given N = 3245 the function should return 55.   Complexity:
  3.  
  4.     expected worst-case time complexity is O(sqrt(N));
  5.     expected worst-case space complexity is O(1).
  6.    
  7. #include <algorithm>
  8. #include <cassert>
  9. #include <cmath>
  10. #include <cstddef>
  11. #include <cstdlib>
  12. #include <iostream>
  13. #include <limits.h>
  14.  
  15. template <typename UnsignedT>
  16. UnsignedT bit_rev(UnsignedT u)
  17. {
  18.     UnsignedT ret = UnsignedT();
  19.  
  20.     std::size_t n;
  21.     for (n = CHAR_BIT * (sizeof (UnsignedT)); n > 0 && !(u & (static_cast<UnsignedT>(0x1) << (n - 1))); --n)
  22.         /* empty */;
  23.  
  24.     std::size_t i;
  25.     for (i = 0; i < n; ++i) {
  26.         ret |= ((u >> i) & 0x1) << (n - i - 1);
  27.     }
  28.     return ret;
  29. }
  30.  
  31. long least_symmetric_binary_root(unsigned long N)
  32. {
  33.     long ret = -1;
  34.  
  35.     unsigned long floor_sqrt_N = static_cast<unsigned long>(std::sqrt(static_cast<long double>(N)));
  36.     while ((floor_sqrt_N + 1) * (floor_sqrt_N + 1) < N) {
  37.         ++floor_sqrt_N;
  38.     }
  39.  
  40.     unsigned long a;
  41.     for (a = 1; a <= floor_sqrt_N; ++a) {
  42.         if (N % a == 0) {
  43.             unsigned long q = N / a;
  44.             if (bit_rev(a) == q) { // `a` is a symmetric binary root of N.
  45.                 return a; // We know that it is the least symmetric binary root.
  46.                 // Proof:
  47.                 // Let (distinct and in ascending order) a_1, ..., a_n be all natural numbers such
  48.                 // that a_k <= sqrt(N) and a_k evenly divides N. Let q_k = N / a_k. For all k, q_k >= sqrt(N).
  49.                 // Suppose that N is such that at least one of { a_k } is a symmetric binary root (this case).
  50.                 // Let a_k be the first symmetric binary root of N (i.e. bit_rev(a_k) == q_k) among a_1, ..., a_n.
  51.                 // It could be that some of { q_1, ..., q_n } are symmetric binary roots, but for all j = 1 .. n, q_j >= sqrt(N) >= a_k.
  52.                 // Also, for j = k + 1 .. n, a_j > a_k. Therefore, a_k is the least symmetric binary root.
  53.             } else if (bit_rev(q) == a) { // `q` is a symmetric binary root of N.
  54.                 ret = (ret == -1 ? q : std::min(ret, static_cast<long>(q)));
  55.             }
  56.         }
  57.     }
  58.  
  59.     return ret;
  60. }
  61.  
  62. int main()
  63. {
  64.     assert(bit_rev(0x0U) == 0U);
  65.     assert(bit_rev(0x80000000U) == 1U);
  66.     assert(bit_rev(0x11U) == 17U);
  67.     assert(bit_rev(0x7094FU) == 496775U);
  68.     assert(bit_rev(0x2EFDB7U) == 3895261U);
  69.  
  70.     std::cout << least_symmetric_binary_root(50UL) << std::endl;
  71.     assert(least_symmetric_binary_root(50UL) == 10L);
  72.     std::cout << least_symmetric_binary_root(286UL) << std::endl;
  73.     assert(least_symmetric_binary_root(286UL) == 22L);
  74.     std::cout << least_symmetric_binary_root(256UL) << std::endl;
  75.     assert(least_symmetric_binary_root(256UL) == 256L);
  76.  
  77.     return EXIT_SUCCESS;
  78. }
  79.    
  80. #include <stdlib.h>
  81. #include <stdio.h>
  82. #include <math.h>
  83.  
  84. // bit-reverse a number, the simple way
  85. static unsigned long bit_rev(unsigned long n){
  86.     unsigned long r = 0;
  87.     while(n){
  88.         r = (r << 1) | (n&1);
  89.         n >>= 1;
  90.     }
  91.     return r;
  92. }
  93.  
  94. // find least symmetric binary root of an odd number
  95. static long int odd_sym_root(unsigned long n){
  96.     unsigned long root_floor = (unsigned long)sqrt(n), r, q;
  97.     // adjust the square root in case it's too small
  98.     while(root_floor*(root_floor+2) < n) ++root_floor;
  99.     // start at the smallest odd number with the same highest set
  100.     // bit as the sqaure root
  101.     r = root_floor;
  102.     r |= r >> 1;
  103.     r |= r >> 2;
  104.     r |= r >> 4;
  105.     r |= r >> 8;
  106.     r |= r >> 16;   // root_floor is < 2^32, so we can stop here
  107.     r = ((r+1)/2)|1;
  108.     while(r <= root_floor){
  109.         q = n/r;
  110.         // check if r divides n, the cofactor has the right number
  111.         // of bits and finally if it's the bit-reversal of r
  112.         if ((n == q*r) && (q < 2*r) && (q == bit_rev(r))){
  113.             return r;
  114.         }
  115.         r += 2;
  116.     }
  117.     // n has no symmetric binary root
  118.     return -1;
  119. }
  120.  
  121. static long int least_symmetric_binary_root(unsigned long n){
  122.     unsigned long m = n;
  123.     unsigned k = 0;
  124.     // find the odd part of n
  125.     while((m&1) == 0){
  126.         ++k;
  127.         m >>= 1;
  128.     }
  129.     // find the least symmetric binary root of odd part
  130.     long int r = odd_sym_root(m);
  131.     // and shift if it has one
  132.     return (r < 0) ? (-1) : (r << k);
  133. }
  134.  
  135. int main(int argc, char *argv[]){
  136.     unsigned long n = (argc > 1) ? strtoul(argv[1],NULL,0) : 25;
  137.     long int r = least_symmetric_binary_root(n);
  138.     if (r < 0){
  139.         printf("No symmetric binary root.n");
  140.     } else {
  141.         printf("Least symmetric binary root: %ldn",r);
  142.     }
  143.     return EXIT_SUCCESS;
  144. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top