Efficient coding practice for RPN programming



#9

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


#10

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


#11

(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.

#12

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.

#13

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

#14

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


#15

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

#16

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


Possibly Related Threads...
Thread Author Replies Views Last Post
  [PRIME] RPN: another attempt at returning more than one value to the RPN stack Marcus von Cube, Germany 5 660 11-05-2013, 02:44 AM
Last Post: Marcus von Cube, Germany
  HHC 2013 RPN Programming Challenge - Final Thought Jeff O. 7 650 10-17-2013, 11:02 AM
Last Post: Jeff O.
  HHC / HP Museum Programming Contest for RPN and RPL machines Gene Wright 18 1,355 09-22-2013, 09:39 AM
Last Post: Miguel Toro
  HHC 2012 RPN Programming Contest - 10-Step Way-After-Nashville Solution Jeff O. 32 2,137 10-12-2012, 01:41 AM
Last Post: Paul Dale
  HHC 2012 RPN Programming Challenge Conundrum Jeff O. 15 972 10-08-2012, 03:34 PM
Last Post: Gerson W. Barbosa
  HHC 2012 RPN Programming Contest Gene Wright 73 2,832 09-28-2012, 12:43 PM
Last Post: x34
  HHC 2012 programming contests coming soon (RPN and RPL) Gene Wright 9 766 09-21-2012, 03:38 PM
Last Post: Paul Dale
  Program Coding Sheets for 33s/35s Matt Agajanian 6 480 03-03-2012, 04:03 PM
Last Post: David Hayden
  Help with RPN programming hpnut 36 2,062 03-03-2012, 09:31 AM
Last Post: Bill (Smithville, NJ)
  Re: RPN Programming exercise (HP-42S) Gerson W. Barbosa 1 234 02-27-2012, 05:51 PM
Last Post: Marcus von Cube, Germany

Forum Jump: