Advertisement
feblehober123

GET Functions and Explaination

Oct 25th, 2014
260
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.24 KB | None | 0 0
  1. Because of le copyright joke, this document is licensed under a Creative Commons Attribution 4.0 International License.
  2. The C implementation, however, is WTF PL (wtfpl.org).
  3.  
  4. The first function, the one that determines the number of repeating digits in a post number, is by far the simpler one. When most programmers are confronted with this problem, they solve it by converting the post number to an array/string, and compare the digits in reverse order. By trying to not use any string conversions I have found a much more efficient and simple technique. The last digit of any integer can be obtained with modulo by 10. Thus, if the integer is repeatedly divided by 10, modulo by 10 will reveal all of the digits in reverse order for comparison. Here is the C implementation:
  5.  
  6. /* repdigits: return the number of repeating digits
  7. * in num, from the right.
  8. * divide by 10 version */
  9. int repdigits(int num)
  10. {
  11. int repdig = 0;
  12. int pdigit = -1; //previous digit
  13. int cdigit = 0; //current digit
  14.  
  15. do {
  16. cdigit = num % 10;
  17. if (cdigit != pdigit && pdigit != -1)
  18. return repdig; //non-repeating digit located
  19. repdig++;
  20. pdigit = cdigit;
  21. } while (num /= 10);
  22. return repdig;
  23. }
  24.  
  25. The second function, the one that determines the next GET based on the current post number, is more complicated, as anybody who has tried to implement it knows. The function can be divided into four tasks. The first is to separate the digits that are to be unchanged, the second is to generate an array of digits to be changed, the third is to determine the repeating digit of the next GET and assemble it into a repeating integer of the GET length, and the fourth is to return the sum of the unchanged digits and the repeating digits.
  26. The first task is simple enough: integer divide by 10^n, then multiply by 10^n to clear the n low order digits. I don't know how modern CPU compute powers and multiplication, so I decided to use this method instead of repeatedly dividing and multiplying by 10 in the hope that hardware acceleration will make it more efficient. Note that you may need to link the math library on your system to compile the C implementation.
  27. The second task is also simple. It uses the repeated modulo paired with division from the first function to generate the array. This task arguably goes against my ideal of not using a string conversion, but after spending a long time considering how the third task would need to access the digits, I decided to use this method. Also, this method only generates as many digits as necessary.
  28. The third task is what makes this function difficult to implement. It is also the part that is most likely to be inefficient or needlessly complicated, and is hard to explain. I suggest if want to really understand how the first part of this task works, you should try flow charting it from the C implementation and drawing out how it modifies and compares the variables. The second part is simple; after the repeating digits is determined, it is multiplied by 10 n times and the repeating digit is add each time.
  29. Finally, the fourth task, simply adds the unchanged digits and the repeating digits and returns the result.
  30.  
  31. code:
  32. int nextget(int num, int n)
  33. {
  34. int unchanged, repdigit, repdigits, i, tpow, digits[n];
  35. unchanged = num;
  36.  
  37. /* separate unchanged digits */
  38. tpow = (int)pow(10,n);
  39. unchanged /= tpow;
  40. unchanged *= tpow; //Erase n low-order digits. Possibly could be more efficient?
  41.  
  42. /* generate array of digits to be changed */
  43. for (i=n-1; i >= 0 && num; i--) {
  44. digits[i] = num % 10;
  45. num /= 10;
  46. }
  47.  
  48. /* run comparisons to determine the repeating digit of the next get */
  49. repdigit = digits[0]; //repdigit must be stored elsewhere so that
  50. //it can be mutated without changing the digits
  51. for (i=0; i < n; i++)
  52. if (digits[0] < digits[i]) {
  53. repdigit++;
  54. if (repdigit > 9)
  55. repdigit = 0;
  56. break;
  57. } else if (digits[0] > digits[i])
  58. break;
  59. if (i==n && digits[0]==digits[i-1]) {
  60. repdigit++;
  61. if (repdigit > 9)
  62. repdigit = 0;
  63. }
  64. /* assemble the repeating digit into a repeating integer of n columns */
  65. repdigits = repdigit;
  66. for (; n > 1; n--)
  67. repdigits = repdigits * 10 + repdigit;
  68.  
  69. /* return the sum of the unchanged digits and the repeating digits */
  70. return unchanged + repdigits;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement