multiplication of 849 by 3 shift and 3 add/subtract [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 9 years ago.

Improve this question

Multiplication by 849 achieved by 3 add/sub and 3 shift operations I have solved till 4 add and 4 add/sub,how can i reduce it further?849 * X= X<<10 -X<<7 -X<<6 + X<<4+ X

Answer 1

Here's the solution. Note you have to use an intermediate variable a, otherwise it's impossible. It uses: ((17 << 6) + 17) - 256 = 849 and that 17 = (1 << 4) + 1.

a = (X << 4) + X
return (a << 6) + a - (X << 8)

I found it by searching possible programs on a stack machine using the code at the end of the answer. The solution was given in the form of a stack program, which I manually translated into the expression above:

['push X', '<<4', 'push X', '+', 'dup 0', '<<6', '+', 'push X', '<<8', '-']

Here's the program... it takes a few minutes to run.

import heapq

def moves(adds, shifts, stack, just_shifted):
    if len(stack) and shifts and not just_shifted:
        for shv in xrange(1, 10):
            yield (adds, shifts-1), '<<%d' % shv, stack[:-1] + [stack[-1] << shv]
    if len(stack) <= adds:
        for i in xrange(len(stack)):
            if stack[i] != 1:
                yield (adds, shifts), 'dup %d' % i, stack + [stack[i]]
    if len(stack) > 1 and adds:
        yield (adds-1, shifts), '+', stack[:-2] + [stack[-2] + stack[-1]]
        yield (adds-1, shifts), '-', stack[:-2] + [stack[-2] - stack[-1]]
    if len(stack) <= adds:
        yield (adds, shifts), 'push X', stack + [1]

def find(target):
    work = []
    heapq.heappush(work, (0, [], 3, 3, []),)
    while work:
        it = heapq.heappop(work)
        print it
        if len(it[1]) == 1 and it[1][-1] == target:
            return it[4]
        just_shifted = len(it[4]) and ('<<' in it[4][-1])
        for nsum, desc, nst in moves(it[2], it[3], it[1], just_shifted):
            nit = (it[0]+1, nst, nsum[0], nsum[1], it[4] + [desc])
            heapq.heappush(work, nit)

print find(849)