HP Forums
Efficient coding practice for RPN programming - Printable Version

+- HP Forums (https://archived.hpcalc.org/museumforum)
+-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html)
+--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html)
+--- Thread: Efficient coding practice for RPN programming (/thread-107997.html)



Efficient coding practice for RPN programming - Les Wright - 02-14-2007

I know this is computer science 101, which I never formally studied, but I somehow recall that computers can do addition faster than multiplication.

I am working on a program for the 33S that has to double the contents of the X register on a couple of occasions, but it does it repetitively, in a loop.

I have the sense, without putting a clock to it, that using "ENTER +" makes things go perceptibly faster than "2 *". How many times the B busy indicator flashes is my quasi timer. In the former situation, it flashes twice then the answer is returned, and in the latter situation, it takes a little longer to flash three times for the same input before returning an answer.

The loop in question is performed 24 times, and I am impressed that with the naked eye I can perceive the slight time savings.

Does this all make sense? Is it generally faster to double a number by adding it to itself than multiplying it by 2? I sense yes.

Les

p.s. on the 41 series and 42S one can ingeniously do it in one step--ST+ X. JM Baillard uses this motif inngeniously in several of his programs in the library.


Edited: 17 Feb 2007, 3:29 p.m. after one or more responses were posted


Re: Efficient coding practice for RRN programming - The person formerly known as dot - 02-14-2007

You could always shift left to multiply by 2. Shifting is very, very fast. Not sure about on that calculator tho.


Re: Efficient coding practice for RRN programming - M G Berberich - 02-14-2007

I somehow recall that computers can do addition faster than multiplication.

That depends. CPUs with a good floating-point-unit nowadays need the same time for fp-addition and fp-multiplication, the same holds for integers. If you want to know for sure for a specific CPU you have to look into the data-sheets or do a test.


Re: Efficient coding practice for RRN programming - Thomas Okken - 02-14-2007

Since most (all?) calculators and PDAs lack floating-point hardware, they have to perform their math in software, usually one digit at a time -- pretty much the way you would do it on paper, really. Done that way, addition takes an amount of time proportional to the number of digits, while multiplication takes an amount of time proportional to the number of digits squared.


Those are worst-case figures, though. A clever multiplication algorithm should be able to do multiplication by 2 in about the same time it takes to add a number to itself. Your observation that multiplying by 2 is significantly slower than the ENTER + sequence could be due to an inefficient multiplication algorithm, or it could be due to the cost of entering a floating-point constant. On the 33S especially, floating-point constants could be inefficient because of the way it uses binary math internally while displaying and accepting numbers in decimal. I'd be interested how the timings change if you were to store the number 2 in a register and used that in your loop.

- Thomas


Re: Efficient coding practice for RPN programming - PeterP - 02-18-2007

Don't know about the 33S, however for the 41, the problem would be the number 2. Entering a number in the 41 is 5-10 times slower than most any other operation. That's why Sto* X is so ingenious - it is also 2 bytes, but much much faster. I don't have access to my tables right now, but I think it is a factor of 5 or so that this is faster than 2, *. It also does not effect the Stack and Reg L...

Cheers

Peter


Re: Efficient coding practice for RPN programming - Vassilis Prevelakis - 02-18-2007

PeterP wrote:

> That's why Sto* X is so ingenious - it is also 2 bytes, but much
> much faster. I don't have access to my tables right now, but I
> think it is a factor of 5 or so that this is faster than 2, *.

You mean STO + X

STO * X is equivalent to X^2

**vp




Re: Efficient coding practice for RRN programming - John Keith - 02-18-2007

(Slightly OT)

On newer RPL calcs, where binary integers are a distinct data type, Shifting is noticeably faster than multiplication or division. On the 49g+,

#2 *   takes 2.85ms
sl takes 1.67ms

This is important since BINTs are faster than reals for looping variables.


Re: Efficient coding practice for RPN programming - John Garza (3665) - 02-19-2007

Test it.

24 repetitions is insignificant. Try looping for a thousand iterations and time it with a stopwatch. Compare results from the addition vs. multiplication methods (or the shift left if you can do it). Divide the time by a thousand to get the time per loop.

-Just a thought.
-J