Large Multiplication..

[randomperson]

Ok.. I've come upon a weird problem that probably doesn't come up very often.. and as I'm not good at math at all (and yet a program.. lol) I just can't figure it out. Here's the problem:

I have a 64-bit number (8 bytes.. so wasteful of memory am I) which I need to multiply by a 8 bit number. Obviously this is a problem as the PBASIC language doesn't support many mathematical functions.. and the stuff it does support is limited to 16 bits I think..

Anyway, any assistance that someone could give would be helpful!

[rbayer]

First, multiplying an 8-bit number and a 64-bit number could give you a 72-bit number if I remember my binary correctly (or maybe it's 71?). Anyway, it's going to be bigger than your original size. Well, my binary's a little rusty, as is my math thanks to winter break, but I'll give this a shot. Assuming your 64-bit number is broken up into 8 byte-sized variables named bigVar1-bigVar8 with 1 being the highest-order byte and 8 being the lowest, and assuming smallVar is your 8-bit number, the formula would look something like this:

result0 var byte
result1 var byte
...
result8 var byte
temp var word

temp=bigVar8 * smallVar
result8= temp & $00FF

temp=temp & $FF00 >> 8 + (bigVar7 * smallVar)
result7=temp & $00FF

temp=temp & $FF00 >> 8 + (bigVar6 * smallVar)
result6=temp & $00FF

temp=temp & $FF00 >> 8 + (bigVar5 * smallVar)
result5=temp & $00FF

...

temp=temp & $FF00 >> 8 + (bigVar1 * smallVar)
result1=temp & $00FF
result0=temp & $FF00 >> 8

Don't quote me on any of that as I haven't tested it yet nor do I even know how I would. Anyway, result1-result8 now have the product and result0 has whatever overflow may have occurred. Anybody want to verify this algorithm/shoot it down? As I said, it may or may not work.

Finally, I have to ask: what possible purpose could you have for a 64-bit number in PBASIC?

[seanwitte]

To multiply two large numbers you can add the 8-byte value to itself multiple times in a loop. You will need to reserve an extra byte for the results. This is probably painfully slow, I do not endorse this at all.

Here is a basic algorithm, I'm not sure whether it will work. I don't see a reason for needing this, but here is a crack at it anyways.

'inputs for the sub that will add the numbers together
bigVar 		VAR BYTE  'pointer to the low-order byte in RAM
resultVar   	VAR BYTE  'pointer to the results in RAM
smallVar    	VAR BYTE  '8-bit operand
numBytes  	VAR BYTE  'number of bytes in bigVar

'working variables
op1           	VAR BYTE
op2           	VAR BYTE
temp     	VAR WORD
position     	VAR BYTE
counter      	VAR BYTE

'64-bit operand starts at ram location 1
'this represents the value $0807060504030201
PUT 1, $01
PUT 2, $02
PUT 3, $03
PUT 4, $04
PUT 5, $05
PUT 6, $06
PUT 7, $07
PUT 8, $08

'set up values for the call to the subrountine
bigVar = 1	'pointer to RAM location for operand 1
resultVar = 10	'pointer to RAM location for results
numBytes = 8	'number of bytes in operand 1
smallVar = 100	'multiply operand 1 by 100

GOSUB FindBigProduct

'now, the results are stored in RAM locations
'10 - 18 (9 bytes total)

'----------------------------------------------
'subroutine to multiply a multi-byte value 
'stored in RAM by a byte. The multi-byte value
'should be stored in sequential RAM locations
'in order from least to most significant byte
'-----------------------------------------------
FindBigProduct:

	'initialize the results to 0. there 
	'will be numBytes + 1 bytes in result
	FOR counter = 0 TO numBytes
		PUT resultVar + counter, 0
	NEXT

	'exit if the other operand is 0
	IF smallVar = 0 THEN FindBigProduct_Return

	'loop through and add the value in 
	'bigVar to itself smallVar times.
	FOR counter = 1 TO smallVar
		'reset the running sum so 
		'that it handles overflow
		temp = 0

		'loop through and add each
		'byte together, saving overflow
		FOR position = 1 TO numBytes
			'get the operands 
			GET bigVar + position - 1, op1
			GET resultVar + position - 1, op2
			
			'add them together
			temp = temp + op1 + op2
			'save the low-order byte
			PUT resultVar + position - 1, temp.byte0
			
			'shift the overflow
			temp = (temp & $FF00) >> 8
		NEXT
	NEXT
	
	'save the highest order byte		
	PUT resultVar + numBytes, temp.byte0

FindBigProduct_Return:

	RETURN

[randomperson]

First, thanks for the assistance..

Second, as to why you need something this large.. two reasons why I posted:

a) another person didn't think it could be done and I did (just didn't know how to do it)

b) for use in a really high-res counter loop related to speed regulation.. we were brainstorming stupid ideas and this happened to come up as part of one of those..

Anyway, thank you much for your assistance!

[seanwitte]

I don't remember for sure, but most languages I've used allocate 4 bytes for a long integer. Thats a range of -2,147,483,648 to 2,147,483,647 for a signed int or 0 - 4,294,967,295 for an unsigned int. You wanted to use an 8-byte number, which is a float data type that has an signed length of about 28 digits.

<EDITED>
Thanks, I was thinking of the IFI controller fixed processor loop, even got it wrong. The stamp runs at 20MHz, 4000 instructions per second. To increment a number from 0 to 4,000,000,000 would take at least:

(1 second/4000 instructions) * 4,000,000,000 instructions =
1,000,000 seconds =
17,000 minutes =
283 hours =
12 days

</EDITED>

[Matt Leese]

The Stamp runs considerably faster than 40 Hz. What you're thinking of is the fact that input data is sent to the Stamp at 20 Hz (I think it's 20 Hz; did I misplace my mind again?). If I remember correctly, the Stamp executes 1000 lines of code every second. It is possible to sit in a loop and execute it for a given period of time. However, you need to remember that if you miss 4 input packets (ie you don't poll for the input data), the Stamp controller will be reset by the master controller. So don't sit in the loop for more than .2 seconds.

Matt

[rbayer]

Originally posted by seanwitte
I don't remember for sure, but most languages I've used allocate 4 bytes for a long integer. Thats a range of -2,147,483,648 to 2,147,483,647 for a signed int or 0 - 4,294,967,295 for an unsigned int. You wanted to use an 8-byte number, which is a float data type that has an signed length of about 28 digits.

<EDITED>
Thanks, I was thinking of the IFI controller fixed processor loop, even got it wrong. The stamp runs at 20MHz, 4000 instructions per second. To increment a number from 0 to 4,000,000,000 would take at least:

(1 second/4000 instructions) * 4,000,000,000 instructions =
1,000,000 seconds =
17,000 minutes =
283 hours =
12 days

</EDITED>

Don't forget that you have considerably more than 4,000,000,000 instructions. In addition to all the addition, you also have instructions to incremement the counter, compare the counter, and do the jump. It's even more complicated than this as a single instruction to add two numbers actually takes 2 "real" instructions if I remember correctly. PBASIC is a compiled language, meaning that almost nothing you type gets translated literally.

Also, just for the record, the Stamp is 50Mhz and does about 10,000 instructions/second. Don't forget that we have the BS2SX, not a BS2. Look here for a good comparison of all the different Stamps.

However, as Matt said, the IFI controllers are quite a bit slower than this. Since the Stamp has no serial buffers, it has to actually wait while sending/receiving any data (Serin/Serout).

[kmcclary]

Originally posted by randomperson
[I needed a value this large] for use in a really high-res counter loop related to speed regulation.. we were brainstorming stupid ideas and this happened to come up as part of one of those..

If there is any branching at all, your loop time will be variable, so don't depend on it if you need a PRECISE time interval (such as "do <this> at EXACTLY 5.5 seconds before the end of the round").

Here's a HARDWARE solution for LONG (multi-second) times that's VERY repeatable: Create a simple one shot timer with a 555, and put it in the Electronics Box. Trigger it with a digital output, and read the status back with a switch input. If you wish a VERY precise time interval, you can make the timer out of a PIC micro, a "long range timer chip" (such as an EXAR XR-2242), or a crystal oscillator brick driving a counter/divider chain and some simple "done" gate logic.

However, since the rules state you may ONLY drive functional robot devices with the RC outputs ("active decorations" are the only exception), in reality you're still limited to the time resolution of One Loop in any case. Therefore, a 555 timer will probably be just as good as something more elaborate. That circuit should only cost a couple of bucks to make.

Don't forget that they MAY stop then continue a round for many reasons, so you should NEVER assume "powerup = start of two minute round"! A multi-minute timer (software OR hardware) to automatically trigger your 'near end of round surprise' may never time out if they stop the round, so you'll also need a driver manual trigger.

- Keith