Four bit adder: Difference between revisions
Content deleted Content added
4-bit adder in ocaml |
→{{header|OCaml}}: slight simplification, and n-bit adder |
||
Line 1,136: | Line 1,136: | ||
let sub nin nout where = { nin=nin; nout=nout; apply=function |
let sub nin nout where = { nin=nin; nout=nout; apply=function |
||
bits -> Array.sub bits where nout };; |
bits -> Array.sub bits where nout };; |
||
let transpose n p v = |
|||
if n*p <> Array.length v |
|||
then failwith "bad dim" |
|||
else |
|||
let w = Array.copy v in |
|||
for i=0 to n-1 do |
|||
for j=0 to p-1 do |
|||
let r = i*p+j and s = j*n+i in |
|||
w.(r) <- v.(s) |
|||
done |
|||
done; |
|||
w;; |
|||
(* line mixing (a special permutation) |
|||
mix 4 2 : 0,1,2,3, 4,5,6,7 -> 0,4, 1,5, 2,6, 3,7 |
|||
unmix: inverse operation *) |
|||
let mix n p = perm (transpose n p (Array.init (n*p) (function x -> x)));; |
|||
let unmix n p = perm (transpose p n (Array.init (n*p) (function x -> x)));; |
|||
(* basic blocks |
(* basic blocks |
||
Line 1,193: | Line 1,214: | ||
(* 4-bit adder *) |
(* 4-bit adder *) |
||
let add4 = block_array serial [| |
let add4 = block_array serial [| |
||
assoc (const false 1) ( |
assoc (const false 1) (mix 4 2); |
||
assoc full_adder (pass 6); |
assoc full_adder (pass 6); |
||
assoc (assoc (pass 1) full_adder) (pass 4); |
assoc (assoc (pass 1) full_adder) (pass 4); |
||
Line 1,227: | Line 1,248: | ||
# plus 0 0;; |
# plus 0 0;; |
||
- : int * int = (0, 0) |
- : int * int = (0, 0) |
||
</lang> |
|||
An extension : n-bit adder, for n <= 64 (n could be greater, but we use Int64 for I/O) |
|||
<lang ocaml> |
|||
(* general adder (n bits with n <= 64) *) |
|||
let gen_adder n = block_array serial [| |
|||
assoc (const false 1) (mix n 2); |
|||
assoc full_adder (pass (2*n-2)); |
|||
block_array serial (Array.init (n-2) (function k -> |
|||
assoc (assoc (pass (k+1)) full_adder) (pass (2*(n-k-2))))); |
|||
assoc (pass (n-1)) full_adder |];; |
|||
let gadd_io n = assoc (gen_adder n) (const false (n-1));; |
|||
let gen_plus n a b = |
|||
let v = Array.map Int64.to_int |
|||
(eval (gadd_io n) n n (Array.map Int64.of_int [| a; b |])) in |
|||
v.(0), v.(1);; |
|||
</lang> |
|||
And a test |
|||
<lang ocaml> |
|||
# gen_plus 7 100 100;; |
|||
- : int * int = (72, 1) |
|||
# gen_plus 8 100 100;; |
|||
- : int * int = (200, 0) |
|||
</lang> |
</lang> |
||