My task is to make a powerfunction that with the use of (2,21) it has to only multiply 11 times, instead of the 21 times. How do I do this?

Heres a normal powerfunction which multiplies (2,21) 21 times.
fun powerNew (a,0)=1
| powerNew (a,n) =a*powerNew(a,n-1);
powerNew(2,21);

Using Emacs and SML

This post was edited by Hej on Sep 5 2013 05:20am

what does that mean? if you're trying to do 2^11 instead of 2^21, just replace 21 with 11. or are you actually trying to do 2^21 but with fewer multiplications?

im trying to do 2^21 with a maximum of 11 multiplications, sorry for the bad description of the task.

heh are you allowed to use division and/or addition?

you could do a = 3^3, then a^7 = 3^21, which only uses 10 multiplications, however; finding those factors of 21 =(3*7), is going to require some liberal use of division, and for larger numbers this will very quickly outpace any potential gains from reducing the number of multiplications.

This post was edited by Azrad on Sep 5 2013 10:23am

written in python, but the logic would be the same:

So that took 9 multiplication operations (of course it inserted some while loops).

if this is a serious project, you should add a check to ensure the the power input is >= 0, that the power input is an integer, that the "number" input is a number, and that that both inputs do not equal 0 at the same time (0^0 is undefined).

This post was edited by Azrad on Sep 5 2013 11:17am

got it in SML Just started studying computer science, and this was one of the tasks in our first assignment.

I suspect the purpose of your assignment is to learn to implement the double and add method used for EC point multiplication, which is the most comon operation in ECDSA (i.e. key signature crypto)

The idea is to decompose 21 into a serie of x2 and +1 until you reach 1, as follows:

21-1 = 20
20/2 = 10
10/2 = 5
5-1 = 4
4/2 = 2
2/2 = 1;

Now performing the steps backwards would take you from 1 to 21 in 6 operations. This easily translates to powers: each +1 means to multiply the value by 2, each *2 turns into a square operation, and thus:

1*2 = 2
2*2 = 4
4+1 = 5
5*2 = 10
10*2 = 20
20+1 = 21

2*2 = 4 (eq. *2)
4*4 = 16 (eq. *2)
16*2 = 32 (eq. +1)
32*32 = 1024 (eq. *2)
1024*1024 = 1048576 (eq. *2)
1048576*2 = 2097152 (eq. +1)

This post was edited by flyinggoat on Sep 5 2013 06:46pm