dense representation, on the other hand, is simply a list (or some other kind of sequence) of digits, including those digits that happen to be 0. For example, this shows two different representations of binary numbers in Standard ML- one dense and one sparse— along with several representative functions on each. structure Dens = struct datatype Digit = Zero ? One type Natural = Digit list (* increasing order of significance, no trailing Zeros*) func increment = One ? increment (Zero :: ds) = One :: ds ?increment (One :: ds) = Zero :: increment ds (* carry*) func decrement One = ? decrement (One :: ds) = Zero :: ds ? decrement (Zero :: ds) = One :: decrement ds (* borrow*) func add (ds, ) = ds ? add ( , ds) = ds ? add (d :: ds1, Zero :: ds2) = d :: add (ds1, ds2) ? add (Zero :: ds1, d :: ds2) = d :: add (ds1, ds2) ? add (One :: ds1, One :: ds2) = Zero :: increment (add (ds1, ds2)) (* carry*) end structure SparseByWeight = struct type Natural = int list (* increasing list of weights, each a power of two*) (* add a new weight to a list, recurse if weight is already present*)
dense representationUpdated January 17, 2019
This essay has been submitted to us by a student. This is not an example of the work written by our writers.