128bit math[started but more is needed.]
mctrivia
Posts: 3,772
ok so I am trying to do 128bit math on a 32bit processor. i remember multiply:
i do not remember how to get the carrys so that part of the code is wrong at present.
but how do i do a modulus?
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
24 bit LCD Breakout Board now in. $21.99 has backlight driver and touch sensitive decoder.
Post Edited (mctrivia) : 1/4/2010 3:03:25 AM GMT
VAR
long x 'holds 128 bit value of x
long M 'holds 128 bit value of M
long t[noparse][[/noparse]9] '8+1 to handle overflow cause by simplified square function.
PUB computebit| i
'Clear t
for i:=0 to 7
t[i]:=0
't=x*x
for i:=0 to 3
for j:=0 to 3
t[noparse][[/noparse]i+j]+=x[i]*x[noparse][[/noparse]j]
t[noparse][[/noparse]i+j+1]+=(x[i]**x[noparse][[/noparse]j])+carry
t[noparse][[/noparse]i+j+2]+=carry
'x=t//M
[/i][/i][/i]
i do not remember how to get the carrys so that part of the code is wrong at present.
but how do i do a modulus?
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
24 bit LCD Breakout Board now in. $21.99 has backlight driver and touch sensitive decoder.
Post Edited (mctrivia) : 1/4/2010 3:03:25 AM GMT
Comments
-Phil
64/32 is easy to do. 128/32 is also easy. the problem is when you want to do 256/128 and return only the remainder that it gets hard. Successive approximation would take forever. Anyone know a cool trick?
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
24 bit LCD Breakout Board now in. $21.99 has backlight driver and touch sensitive decoder.
propeller.wikispaces.com/MATH
I wish someone would put the code on this page into a wrapper so it is easy to use. I'm not up to it.
Rgds, David
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
24 bit LCD Breakout Board now in. $21.99 has backlight driver and touch sensitive decoder.
need to multiply to 64bit prime numbers together.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
24 bit LCD Breakout Board now in. $21.99 has backlight driver and touch sensitive decoder.
The code doesn't work as it is. I assume the result is kept in the txxx registers.... call instructions are lacking a '#' but that is not the biggest problem.... I'll see if I can fix it.
Edit: this code works
DAT org entry '*********************************************************************** '* t:=x*x * '* Modified by Ale(500) * '*********************************************************************** '* Notes: * '* squaring a 128bit number on a 32bit system is a very long process * '* but there are some short cuts that can be taken. * '* if x is are 128bit number and is made up of 4 longs DCBA D being * '* most significant then we can square x by doing the following * '* multiplications: * '* AA+ * '* AB*10+ * '* AC*100+ * '* AD*1000+ * '* BA*10+ * '* BB*100+ * '* BC*1000+ * '* BD*10000+ * '* CA*100+ * '* CB*1000+ * '* CC*10000+ * '* CD*100000+ * '* DA*1000+ * '* DB*10000+ * '* DC*100000+ * '* DD*1000000 * '* * '* Since A*B=B*A this can be shortened to: * '* A*A * '* B*B*100+ * '* C*C*10000+ * '* D*D*1000000+ * '* A*B*2*10+ * '* A*C*2*100+ * '* A*D*2*1000+ * '* B*C*2*1000+ * '* B*D*2*10000+ * '* C*D*2*100000+ * '* by putting the squared values first we do not need to worry about * '* zeroing are resulting are first. * '*********************************************************************** ' ------------ Argument -------------- ||| ------------- Result ------------- ||| Cycles ' ' 00000000 00000000 00000000 00000000 ||| v00000000 00000000 00000000 00000000 ' 00000000 00000000 00000000 00000001 ||| v00000000 00000000 00000000 00000001 ||| 172 ' 00000000 00000000 00000000 0000000F ||| v00000000 00000000 00000000 000000E1 ||| 484 ' 00000000 00000000 00000000 F0000000 ||| v00000000 00000000 E1000000 00000000 ||| 2500 ' 00000000 00000000 00000000 FFFFFFFF ||| v00000000 00000000 FFFFFFFE 00000001 ||| 3396 ' 00000000 00000000 FFFFFFFF 00000000 ||| vFFFFFFFE 00000001 00000000 00000000 ||| 9096 ' FFFFFFFF 00000000 00000000 00000000 ||| vFFFFFFFE 00000001 00000000 00000000 << 64 ||| 19404 ' FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF ||| vFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE 00000000 00000000 00000000 00000001 ||| 13380 ' ' ' ' mult128 mov thhh,#0 mov thhl,#0 mov thlh,#0 mov thll,#0 mov tlhh,#0 mov tlhl,#0 mov tllh,#0 mov tlll,#0 mov xhhh,#0 mov xhhl, #0 mov xhlh, #0 mov xhll, #0 mov yhh, xlhh mov yhl, xlhl mov ylh, xllh mov yll, xlll m128loop shr yhh, #1 wc rcr yhl, #1 wc rcr ylh, #1 wc rcr yll, #1 wc if_nc jmp #m128loop2 add tlll, xlll wc addx tllh, xllh wc addx tlhl, xlhl wc addx tlhh, xlhh wc addx thll, xhll wc addx thlh, xhlh wc addx thhl, xhhl wc addx thhh, xhhh m128loop2 shl xlll, #1 wc rcl xllh, #1 wc rcl xlhl, #1 wc rcl xlhh, #1 wc rcl xhll, #1 wc rcl xhlh, #1 wc rcl xhhl, #1 wc rcl xhhh, #1 mov tt, yhh or tt, yhl or tt, ylh or tt, yll tjnz tt,#m128loop ende2 jmp #ende2 mult128_ret ret 'local vars yll long 0 ylh long 0 yhl long 0 yhh long 0 tt long 0 'global vars ibuffer long 0 lopnum long 32 xhhh long 0 xhhl long 0 xhlh long 0 xhll long 0 xlhh long $ffffffff xlhl long $ffffffff xllh long $ffffffff xlll long $ffffffff 'temp thhh long 0 thhl long 0 thlh long 0 thll long 0 tlhh long 0 tlhl long 0 tllh long 0 tlll long 0 tC long 0 ptoBuff long 0 {{ ' Permission is hereby granted, free of charge, to any person obtaining ' a copy of this software and associated documentation files ' (the "Software"), to deal in the Software without restriction, ' including without limitation the rights to use, copy, modify, merge, ' publish, distribute, sublicense, and/or sell copies of the Software, ' and to permit persons to whom the Software is furnished to do so, ' subject to the following conditions: ' ' The above copyright notice and this permission notice shall be included ' in all copies or substantial portions of the Software. ' ' THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, ' EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF ' MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. ' IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY ' CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, ' TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE ' SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. }}▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Visit some of my articles at Propeller Wiki:
MATH on the propeller propeller.wikispaces.com/MATH
pPropQL: propeller.wikispaces.com/pPropQL
pPropQL020: propeller.wikispaces.com/pPropQL020
OMU for the pPropQL/020 propeller.wikispaces.com/OMU
Post Edited (Ale) : 1/7/2010 1:56:41 PM GMT
Why multiply more than once? The Propeller doesn't have a multiply instruction.
Use the shift and conditional add method for multiplying any number of bits.
Instead of 32 loops for a LONG you have 128 or 256 loops for that many bits and that does the whole multiplication.
For only 256 bits you could even do a long division (like in elementary school) to get the remainder.
You might not need any more than 1024 bits of chalkboard space since you don't need to remember
math that has already finished and has given answers, you know, all the numbers that go down the chalkboard
every time you get another digit of the answer, you can erase and forget, because you don't need to use them again.
I don't think there is anything good or evil for prime numbers here.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
24 bit LCD Breakout Board now in. $24.99 has backlight driver and touch sensitive decoder.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Visit some of my articles at Propeller Wiki:
MATH on the propeller propeller.wikispaces.com/MATH
pPropQL: propeller.wikispaces.com/pPropQL
pPropQL020: propeller.wikispaces.com/pPropQL020
OMU for the pPropQL/020 propeller.wikispaces.com/OMU