Message Boards Message Boards

GROUPS:

An algorithm on divisibility

Posted 8 days ago
153 Views
|
4 Replies
|
3 Total Likes
|

I put on your consideration this algorithm to know if an odd number S is divisible by another number (called "primo" here) :

DivisibleQ[S_, primo_ ] (*  S is odd and primo>5 *) := 
 Module[{factor = ModularInverse[primo - 10, primo] , numero = S}, 
  While[numero > primo, 
   numero = FromDigits[Most[IntegerDigits[numero]]] - factor * Last[IntegerDigits[numero]]]; 
  If [numero < 0, While[numero < 0, numero = numero + primo], 
   While[numero > 0, numero = numero - primo]]; 
  If[numero == 0, True, False]]

Very simple, fast, general and economic. I hope you like it. Free to use naming the source; I named it EGP algorithm. I post it here because I want to share it with all the users of Mathematica. All suggestions are welcome.

4 Replies
Posted 7 days ago

Thank you sooo much, Mr. Lichtblau. I'd been trying the method with other bases; you just have saved me a lot of work. I appreciate your help very much.

Interesting. I will make a few observations and offer a recoding.

(1) Working in base 10 is computationally inefficient. If the digit length is n, then the algorithmic complexity of IntegerDigits/FromDigits becomes n log(n) whereas is is just n in base power-of-2 (because the underlying storage is base 2).

(2) Another advantage to working in a power-of-2 base is that now the prime 5 is not disallowed. Also there is no restriction to primes, the only restriction is that the putative divisor not be even.

(3) It is not necessary to convert to/from a digit string in the main loop. One can let the hex (or base 10) digits become negative. The issue we want to avoid from these conversions is that each iteration then has more work to do.

Here is my recoding using hex.

divisibleQ2[s_, primo_] := 
 Module[{factor = ModularInverse[-16, primo], numero = s, digits, plen, diff},
  digits = IntegerDigits[numero, 16];
  plen = Length[IntegerDigits[primo, 16] + 1];
  While[
   Length[digits] > plen + 1,
   diff = IntegerDigits[factor*Last[digits], 16, Length[digits] - 1];
   digits = Most[digits] - Sign[Last[digits]]*diff;
   ];
  numero = FromDigits[digits, 16];
  If[numero < 0, While[numero < 0, numero = numero + primo], 
   While[numero > 0, numero = numero - primo]]; 
  If[numero == 0, True, False]]

I have not thoroughly tested it but I believe it works correctly. Or at least could be made to.

The down side: it is still algorithmically O(n^2) because it needs O(n) iterations and each operates on lists of length O(n). So it does not beat "schoolkid" (used to be "schoolboy") division by more than a constant factor. Still, it's interesting.

Posted 8 days ago

I am not only sharing the algorithm, but the principle inside for research purposes. I think it is a novel algorithm because of that: the use of the modular inverse the way it uses it. I didn't compare it with the built-in Divisible, but it can be done, I guess ... I don't know which is the algorithm on Divisible. It could be useful if somebody tests this one or put it to work together with another one. I spent a lot of hours working on it, so any opinion, suggestion will be appreciated.

I am only sharing. Thanks for posting here.

What are the advantages of using this algorithm rather than the built-in Divisible?

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract