| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1091.1 | | TRACE::GILBERT | Ownership Obligates | Tue Jun 27 1989 11:15 | 5 |
| Yes, M=2N+1 suffices.
Is there a linear-time squaring algorithm using this representation?
I don't know. Check volume 2 of "The Art of Computer Programming",
by Donald Knuth.
|
| 1091.2 | | RDVAX::NG | | Tue Jun 27 1989 11:49 | 7 |
| Re .1
I've checked Knuth. For multi-precision multiply, the problem is
still unsolved. I think this would apply to square too. Anyway,
there is no special attention to just square. In this case, it
is a special form that I want to square, I was wondering if there
are any tricks to it.
|
| 1091.3 | | RDVAX::NG | | Wed Jun 28 1989 11:28 | 5 |
| I have a related question:
Given a sum of powers of two with coefficients equal -1, 0 or 1,
is there a way to reduce the sum to another that represents the
same value and has the minimal number of non-zero terms?
|
| 1091.4 | too many choices | NIZIAK::YARBROUGH | I PREFER PI | Wed Jun 28 1989 17:24 | 8 |
| > Given a sum of powers of two with coefficients equal -1, 0 or 1,
> is there a way to reduce the sum to another that represents the
> same value and has the minimal number of non-zero terms?
I think this is optimal: If the most significant digit is 1, put the sum in
a canonical form in which only the coeff's 0 and 1 appear. Now replace a
zero followed by a sequence of 3 or more 1's by {10..0-1}. If the most
significant digit is -1, use the canonical form with only 0 and -1, etc.
|
| 1091.5 | One Plus: | DWOVAX::YOUNG | Sharing is what Digital does best. | Wed Jun 28 1989 23:38 | 9 |
| After applying Lynn's rule in .4:
replace all and
{-1 1} { 1-1}
with
{ 0-1} { 0 1}
Apply this rule (and Lynn's) repeatdly until no transformations
remain.
|