mgv@duke.UUCP (Marco G. Valtorta) (06/16/85)
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 been 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.
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 3 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!mgvmgv@duke.UUCP (Marco G. Valtorta) (06/18/85)
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