I'm struggling with mathematical proof of this algorithm, which I have found in a textbook, but unfortunately there is no solution available. I have already proved it when c is >= z and have no idea how to continue.
Here is algorithm:
y and z are natural numbers, c is natural constant c>=2
function multiply(y,z)
1. if z=0 then return(0) else
2. return(multiply(cy,[z/c]) + y*(z mod c))