171 lines
4.8 KiB
Prolog
171 lines
4.8 KiB
Prolog
:- module('bt_mult.pl', [op(850, xfx, btmult),
|
|
btmult/2,
|
|
multiplication/3
|
|
]).
|
|
|
|
:- use_module('bt_add.pl').
|
|
|
|
:- op(850, xfx, btmult).
|
|
A is B btmult C :-
|
|
multiplication(B, C, A).
|
|
|
|
neg(A, B) :-
|
|
maplist(opp, A, B).
|
|
|
|
opp(48, 48).
|
|
opp(45, 43).
|
|
opp(43, 45).
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
% the multiplication (efficient)
|
|
% multiplication(+BIn, +QIn, -AOut)
|
|
% Aout is BIn * QIn
|
|
% BIn, QIn, AOut are strings
|
|
multiplication(BIn, QIn, AOut) :-
|
|
string_to_list(BIn, B),
|
|
string_to_list(QIn, Q),
|
|
|
|
% We work with positive numbers
|
|
( B = [45 | _] -> Pos0 = false, neg(B,BP) ; BP = B, Pos0 = true),
|
|
( Q = [45 | _] -> neg(Q, QP), select(Pos0, [true, false], [Pos1]); QP = Q, Pos1 = Pos0),
|
|
|
|
multiplication_(BP, QP, [48], A),
|
|
( Pos1 = false -> neg(A, A1); A1 = A),
|
|
string_to_list(AOut, A1).
|
|
|
|
|
|
multiplication_(_B, [], A, A).
|
|
|
|
multiplication_(B, [H | T], A, AF) :-
|
|
multiplication_1(B, H, B1),
|
|
append(A, [48], A1),
|
|
bt_add1(B1, A1, A2),
|
|
multiplication_(B, T, A2, AF).
|
|
|
|
% by 1 (digit '+' code 43)
|
|
multiplication_1(B, 43, B).
|
|
|
|
% by 0 (digit '0' code 48)
|
|
multiplication_1(_, 48, [48]).
|
|
|
|
% by -1 (digit '-' code 45)
|
|
multiplication_1(B, 45, B1) :- neg(B, B1).
|
|
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
% the division (efficient)
|
|
% division(+AIn, +BIn, -QOut, -ROut)
|
|
%
|
|
division(AIn, BIn, QOut, ROut) :-
|
|
string_to_list(AIn, A),
|
|
string_to_list(BIn, B),
|
|
length(B, LB),
|
|
length(A, LA),
|
|
Len is LA - LB,
|
|
( Len < 0 -> Q = [48], R = A
|
|
; neg(B, NegB), division_(A, B, NegB, LB, Len, [], Q, R)),
|
|
string_to_list(QOut, Q),
|
|
string_to_list(ROut, R).
|
|
|
|
|
|
division_(A, B, NegB, LenB, LenA, QC, QF, R) :-
|
|
% if the remainder R is negative (last number A), we must decrease the quotient Q, annd add B to R
|
|
( LenA = -1 -> (A = [45 | _] -> positive(A, B, QC, QF, R) ; QF = QC, A = R)
|
|
; extract(LenA, _, A, AR, AF),
|
|
length(AR, LR),
|
|
|
|
( LR >= LenB -> ( AR = [43 | _] ->
|
|
bt_add1(AR, NegB, S), Q0 = [43],
|
|
% special case : R has the same length than B
|
|
% and his first digit is + (1)
|
|
% we must do another one substraction
|
|
( (length(S, LenB), S = [43|_]) ->
|
|
bt_add1(S, NegB, S1),
|
|
bt_add1(QC, [43], QC1),
|
|
Q00 = [45]
|
|
; S1 = S, QC1 = QC, Q00 = Q0)
|
|
|
|
|
|
; bt_add1(AR, B, S1), Q00 = [45], QC1 = QC),
|
|
append(QC1, Q00, Q1),
|
|
append(S1, AF, A1),
|
|
strip_nombre(A1, A2, []),
|
|
LenA1 is LenA - 1,
|
|
division_(A2, B, NegB, LenB, LenA1, Q1, QF, R)
|
|
|
|
; append(QC, [48], Q1), LenA1 is LenA - 1,
|
|
division_(A, B, NegB, LenB, LenA1, Q1, QF, R))).
|
|
|
|
% extract(+Len, ?N1, +L, -Head, -Tail)
|
|
% remove last N digits from the list L
|
|
% put them in Tail.
|
|
extract(Len, Len, [], [], []).
|
|
|
|
extract(Len, N1, [H|T], AR1, AF1) :-
|
|
extract(Len, N, T, AR, AF),
|
|
N1 is N-1,
|
|
( N > 0 -> AR = AR1, AF1 = [H | AF]; AR1 = [H | AR], AF1 = AF).
|
|
|
|
|
|
|
|
positive(R, _, Q, Q, R) :- R = [43 | _].
|
|
|
|
positive(S, B, Q, QF, R ) :-
|
|
bt_add1(S, B, S1),
|
|
bt_add1(Q, [45], Q1),
|
|
positive(S1, B, Q1, QF, R).
|
|
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
% "euclidian" division (inefficient)
|
|
% euclide(?A, +BIn, ?Q, ?R)
|
|
% A = B * Q + R
|
|
euclide(A, B, Q, R) :-
|
|
mult(A, B, Q, R).
|
|
|
|
|
|
mult(AIn, BIn, QIn, RIn) :-
|
|
( nonvar(AIn) -> string_to_list(AIn, A); A = AIn),
|
|
( nonvar(BIn) -> string_to_list(BIn, B); B = BIn),
|
|
( nonvar(QIn) -> string_to_list(QIn, Q); Q = QIn),
|
|
( nonvar(RIn) -> string_to_list(RIn, R); R = RIn),
|
|
|
|
% we use positive numbers
|
|
( B = [45 | _] -> Pos0 = false, neg(B,BP) ; BP = B, Pos0 = true),
|
|
( (nonvar(Q), Q = [45 | _]) -> neg(Q, QP), select(Pos0, [true, false], [Pos1])
|
|
; nonvar(Q) -> Q = QP , Pos1 = Pos0
|
|
; Pos1 = Pos0),
|
|
( (nonvar(A), A = [45 | _]) -> neg(A, AP)
|
|
; nonvar(A) -> AP = A
|
|
; true),
|
|
|
|
% is R instancied ?
|
|
( nonvar(R) -> R1 = R; true),
|
|
% multiplication ? we add B to A and substract 1 (digit '-') to Q
|
|
( nonvar(Q) -> BC = BP, Ajout = [45],
|
|
( nonvar(R) -> bt_add1(BC, R, AP) ; AP = BC)
|
|
% division ? we substract B to A and add 1 (digit '+') to Q
|
|
; neg(BP, BC), Ajout = [43], QP = [48]),
|
|
|
|
% do the real job
|
|
mult_(BC, QP, AP, R1, Resultat, Ajout),
|
|
|
|
( var(QIn) -> (Pos1 = false -> neg(Resultat, QT); Resultat = QT), string_to_list(QIn, QT)
|
|
; true),
|
|
( var(AIn) -> (Pos1 = false -> neg(Resultat, AT); Resultat = AT), string_to_list(AIn, AT)
|
|
; true),
|
|
( var(RIn) -> string_to_list(RIn, R1); true).
|
|
|
|
% @arg1 : divisor
|
|
% @arg2 : quotient
|
|
% @arg3 : dividend
|
|
% @arg4 : remainder
|
|
% @arg5 : Result : receive either the dividend A
|
|
% either the quotient Q
|
|
mult_(B, Q, A, R, Resultat, Ajout) :-
|
|
bt_add1(Q, Ajout, Q1),
|
|
bt_add1(A, B, A1),
|
|
( Q1 = [48] -> Resultat = A % a multiplication
|
|
; ( A1 = [45 | _], Ajout = [43]) -> Resultat = Q, R = A % a division
|
|
; mult_(B, Q1, A1, R, Resultat, Ajout)) .
|