Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site duke.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!unc!mcnc!duke!mgv
From: mgv@duke.UUCP (Marco G. Valtorta)
Newsgroups: net.math
Subject: Composition of "truncated multiplications"
Message-ID: <5941@duke.UUCP>
Date: Tue, 18-Jun-85 13:51:29 EDT
Article-I.D.: duke.5941
Posted: Tue Jun 18 13:51:29 1985
Date-Received: Thu, 20-Jun-85 20:01:56 EDT
Organization: Duke University
Lines: 56

My previous posting of this query contained an error and an omission:
(a) in the example, f3(4) = 2, not 3; (b) 0 <= x <= 1 in the
definition of truncated multiplication of order m.
Thanks to Lambert Meertens of CWI, Amsterdam, who pointed this out.
I submit a corrected query.

I wonder whether this problem, which arose in some work I am doing
on the synthesis of "weights" for rule-based systems, has already
being solved. (By this I mean: is there a known efficient algorithm
to solve this problem, or has it being shown that it is hard?)

I define a truncated multiplication of order m to be a 
finite function f: A -> A, where A = {0,1,...,m},
such that f(x) = floor(x*n), 0 <= n <= m, 0 <= x <= 1.
Note that there are as many truncated multiplications of order m
as there are Farey fractions of order m.
For example, if m=4, the truncated multiplications (with the
corresponding Farey fractions in parenthesis) are:

    f1(1) f2(3/4) f3(2/3) f4(1/2) f5(1/3) f6(1/4) f7(0)
4   4     3       2       2       1       1       0
3   3     2       2       1       1       0       0
2   2     1       1       1       0       0       0
1   1     0       0       0       0       0       0
0   0     0       0       0       0       0       0

Here comes the problem.

Instance: an integer m, a finite functions h: A -> A, where
A = {0,1,...,m}.

Question: Is there a composition of truncated multiplications
of order m that is equal to h?

A particular instance of this problem is:

Is there a composition of truncated multiplications of order 4 
(they are listed above as f1-f7), which is equal to
      4 -> 2
      3 -> 1
h =   2 -> 0   ?
      1 -> 0
      0 -> 0

(Note that h is different from each of f1-f7.  Also, the answer is
"yes," since h is equal to the composition of f2 with itself.)

It seems that the problem would have been studied in the context
of computer arithmetic, but a quick literature search was unsuccessful.
Any ideas will be welcome.

					Marco Valtorta
					Department of Computer Science
					Duke University
					mgv@duke
					...mcnc!duke!mgv