Repeating Decimals

/* frac_dec(N, D, X, Ys, Zs) is true if, in the decimal representation of    */
/*   N/D, X is the integer part, Ys are the digits in the non-repeating      */
/*   fractional part, and Zs are the digits in the repeating fractional part.*/
/* e.g. frac_dec(101, 56, X, Ys, Zs) gives X = 1, Ys = [8,0,3],              */
/*   and Zs = [5,7,1,4,2,8]) indicating that 101/56 = 1.803571428571428...   */
frac_dec(N, D, X, Ys, Zs):-frac_dec(N, D, 10, X, Ys, Zs).

% e.g. frac_dec(1, 19, 2, X, Ys, Zs) gives X = 0, Ys = [],
%   and Zs = [0,0,0,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1] 
frac_dec(N, D, Base, X, Ys, Zs):-
  N >= 0, D > 0, Base > 1,
  X is N // D,
  N1 is N mod D,
  frac_dec_1(N1, D, Base, [], Ms, M, Ws),
  frac_dec_2(Ms, M, Ws, Ys, Zs).

frac_dec_1(0, _, _, _, [], 0, []):-!. % No cycle exists
frac_dec_1(N, _, _, Ns, [], N, []):-
  member(N, Ns), !.                   % A cycle has been found
frac_dec_1(N, D, Base, Ns, [N|Ms], M, [W|Ws]):-
  T is N * Base,
  W is T // D,
  N1 is T mod D,
  frac_dec_1(N1, D, Base, [N|Ns], Ms, M, Ws).

frac_dec_2([], _, Ws, Ws, []).
frac_dec_2([M|_], M, Ws, [], Ws):-!.
frac_dec_2([_|Ms], M, [W|Ws], [W|Ys], Zs):-
  frac_dec_2(Ms, M, Ws, Ys, Zs).

/* member(X, Xs) is true if the element X is contained in the list Xs.       */
%member(X, [X|_]).
%member(X, [_|Xs]):-member(X, Xs).

LPA Index     Home Page

Valid HTML 4.0 Strict