Index
> Main > math question about balanced ternary representation |
| Author |
|
|
revolution 17 May 2019, 14:23
This is similar to the decimal conversion.
There are two general approaches. 1) work from the top down, or 2) work from the bottom up. I think going from the bottom up is easier. 1) Keep dividing by 3 and save the remainder at each step. 2) output the remainders in reverse order for printing in human big-endian readable form, or output the remainders in forward order for some other processing. |
|||
17 May 2019, 14:23 |
|
|
ProMiNick 17 May 2019, 16:19
revolution, I think balanced ternary have a couple of surprises:
for example 2 represented as 3 and as (-1) - so dividing such numbers on 3 will result to garbage. |
|||
|
17 May 2019, 16:19 |
|
|
revolution 17 May 2019, 16:26
I might have misunderstood. I though you were converting from a binary number to trinary form.
But now that I read it again perhaps you are going the other way, from trinary to binary? If so then take each digit starting from the most significant and convert it to 0, 1, 2 form. To add each additional digit multiply the sum by three and add the next digit. If you are doing something else, then I don't know what it is, please explain with an example. |
|||
|
17 May 2019, 16:26 |
|
|
ProMiNick 17 May 2019, 18:24
Numeric systems with even base have no balanced form.(but odd bases have).
Balanced - it is mean that digits in basis are simmetric from zero. In balanced ternary are (-1) (0) (+1). In such systems NOT and NEG are completely identic operations. So needance in next digit in ternary grows up from (1,5) degree not from 3. So every number that absolute value is greater than 1,5 requires 2 ternary digits. that greater than 4,5 requires 3 ternari digits, that greater than 13,5 requires 4 ternary digits and so on. let i=-1 digit, 0=0, and 1=1 -13 = iiit, -12 = ii0t, -11 = ii1t, -10 = i0it, -9 = i00t, -8 = i01t, -7 = i1it, -6 = i10t, -5 = i11t, -4 = 0iit, -3 = 0i0t, -2 = 0i1t, -1 = 00it, 0 = 000t, 1 = 001t, 2 = 01it, 3 = 010t, 4 = 011t, 5 = 1iit, 6 = 1i0t, 7 = 1i1t, 8 = 10it, 9 = 100t, 10 = 101t, 11 = 11it, 12 = 110t, 13 = 111t, |
|||
|
17 May 2019, 18:24 |
|
|
revolution 17 May 2019, 18:28
Okay, so which way are you converting. To, or from, trinary?
You can simply convert "i" to 2 and it becomes a simple trinary number. Nothing special needs to be done when converting. |
|||
|
17 May 2019, 18:28 |
|
|
ProMiNick 17 May 2019, 18:45
I wish to use fasmg as assembler of BCBTD (binary coded balanced ternary data) files.
file format: 9 bytes of positivecomponent of 8 trytes, than 9 bytes of negative, than same for next 8 trytes and so on... so I want to work in fasmg with usual decimal or hexadecimal numbers, but stroring them to file as balanced ternary in positive-negative components. component separation is when trit is (+1) it stored to positives bit, when trit is (-1) it stored to negatives bit. And then I going to introduce ternary instruction sets. But for start I need macro realization of ternaryness itself. |
|||
|
17 May 2019, 18:45 |
|
|
revolution 17 May 2019, 19:10
What are you having trouble with? The conversion? The storage? The fasmg code?
|
|||
|
17 May 2019, 19:10 |
|
|
ProMiNick 17 May 2019, 21:04
At current stage I have problem with mathematic. step2 of algoritm
log2(3)=1,58496250072.... so I can find with bsr highest bit of value and than divide it by 1,5 I will got highest trit or one(or one and half for balanced equal to two) trit above highest. so I going to test algorithm. |
|||
|
17 May 2019, 21:04 |
|
|
revolution 17 May 2019, 21:06
What are you trying to do? Convert to trinary? Convert from trinary? Something else?
You shouldn't need any log functions for base conversion. You only need division. |
|||
|
17 May 2019, 21:06 |
|
|
ProMiNick 17 May 2019, 22:02
fasmged algorithm in very raw form:
Code: macro extract_components value,size:0,outpos:0,outneg:0 local v,?sign,idx,previdx,num,diff v = value previdx=0 while v ;step1 ?sign = 0 if v<0 ?sign = 1 v = -v end if ;step2 idx = (bsr v)*2/3 if ~previdx if idx <2 idx =2 end if num =9 repeat idx-2 num=num*3 end repeat else repeat previdx-idx num=num/3 end repeat end if repeat 3 diff=v-num if diff>0 if diff<num/2 if ?sign outneg = outneg or 1 shl idx else outpos = outpos or 1 shl idx end if break else err You should never see that - it means algorithm is wrong end if else if -diff<num/2 if ?sign outneg = outneg or 1 shl idx else outpos = outpos or 1 shl idx end if break else idx=idx-1 num=num/3 end if end if if %=%% err You should never see that - it means algorithm is wrong end if end repeat ;step3 if (~previdx)&size assert size*9>=idx end if previdx=idx v = diff ;step4 end while end macro |
|||
|
17 May 2019, 22:02 |
|
|
ProMiNick 17 May 2019, 23:05
Code: macro disphex number*,digits:8 repeat digits digit = ((number) shr ((%%-%) shl 2)) and 0Fh if digit < 10 display '0'+digit else display 'A'+digit-10 end if end repeat end macro macro extract_components value,size:0,outpos:0,outneg:0 local v,?sign,idx,previdx,num,diff v = value previdx=0 while v ;step1 ?sign = 0 if v<0 ?sign = 1 v = -v end if ;step2 idx = (bsr v)*2/3 display "suspected idx:" disphex idx display 13,10 if ~previdx if idx <2 idx =2 end if num =9 repeat idx-2 num=num*3 end repeat else repeat previdx-idx num=num/3 end repeat end if display "corrected idx:" disphex idx display 13,10 display "test num:" disphex num display 13,10 repeat 3 diff=v-num display "diff:" if diff>0 disphex diff display 13,10 if diff<=num/2 |diff=1 if ?sign outneg = outneg or 1 shl idx else outpos = outpos or 1 shl idx end if display "got bit",13,10 disphex outpos display ":" disphex outneg display 13,10 break else if idx>2 err You should never see that(1) - it means algorithm is wrong end if else disphex -diff display 13,10 if -diff<=num/2 |diff=-1 if ?sign outneg = outneg or 1 shl idx else outpos = outpos or 1 shl idx end if display "got bit",13,10 disphex outpos display ":" disphex outneg display 13,10 break else idx=idx-1 num=num/3 end if end if if %=%% err You should never see that(2) - it means algorithm is wrong end if end repeat ;step3 if (~previdx)&size assert size*9>=idx end if previdx=idx v = diff ;step4 end while end macro macro test local pos,neg pos = 0 neg = 0 extract_components -2,,pos,neg display "result",13,10 disphex pos display ":" disphex neg display 13,10 end macro test results are incorrect, so problem in math or I incorrect translate algorithm to fasmg syntax or maked too many assumptions. |
|||
|
17 May 2019, 23:05 |
|
|
Tomasz Grysztar 17 May 2019, 23:10
As suggested by the bit about conversion from ternary on Wikipedia, it should be possible to do just a plain conversion to base 3 but replace every digit 2 with (two digits) 1T.
Here's my attempt: Code: Number = +"a big number something like this or bigger" assert Number > 0 virtual Carry = 0 while Number Digit = Carry + Number mod 3 Number = Number / 3 if Digit < 2 Carry = 0 else Digit = Digit - 3 Carry = 1 end if if Digit = -1 db 'T' else db '0' + Digit end if end while if Carry db '0' + Carry end if load BalancedTernary:$-$$ from $$ BalancedTernary = BalancedTernary bswap lengthof BalancedTernary end virtual display BalancedTernary |
|||
|
17 May 2019, 23:10 |
|
|
ProMiNick 18 May 2019, 12:39
Tomasz, thanks. thour solutions are best as always.
displaying ternary is very useful too/ I adapt this to my task "extract binary coded balanced ternary from number".(ternary machines was work with ternary registers & ternary ram, but other media they work on was binary. for that purpose BCBTD was needed.) Code: macro extract_components value,outpos:0,outneg:0,size:0 local Number,?sign,idx,previdx,num,diff if value Number=value if Number<0 ?topos = -1 Number = -Number else ?topos = 1 end if Carry=0 while Number Digit = Carry + Number mod 3 Number = Number / 3 if Digit < 2 Carry = 0 else Digit = Digit - 3 Carry = 1 end if if Digit = ?topos outpos = outpos or 1 shl (%-1) else if Digit = -?topos outneg = outneg or 1 shl (%-1) end if if ~Number if Carry = ?topos outpos = outpos or 1 shl % else if Carry = -?topos outneg = outneg or 1 shl % end if end if end while end if end macro for testing values I used couple of obsolet e macros (they are workable too, I was lazy to search for optimized ones) Code: macro dispBin num*, padding:9, leader, trailer, size local digCount,number,lastdig number = size num lastdig = number if number < 0 display '-' number = -(number shr 1 + number and 1) lastdig = -(lastdig + number + number) else number = number shr 1 lastdig = lastdig and 1 end if digCount = 0 while number shr digCount > 0 digCount = digCount + 1 end while match any, leader display leader end match if padding if digCount < padding repeat (padding-digCount-1) display '0' end repeat end if end if repeat digCount display number shr (digCount-%) and 1+'0' end repeat display lastdig+'0' match any, trailer display trailer end match end macro macro dispDec num*, padding:0, leader, trailer local digCount,tenPow,number,lastdig number = num lastdig = number if number < 0 display '-' number = (-(number shr 1 + number and 1)) / 5 lastdig = -(lastdig + number*5 + number*5) else number = number/10 lastdig = lastdig mod 10 end if digCount = 0 tenPow = 1 while tenPow <= number tenPow = tenPow*10 digCount = digCount + 1 end while match any, leader display leader end match if padding if digCount < padding repeat (padding-digCount-1) display '0' end repeat end if end if repeat digCount tenPow = tenPow/10 display number/tenPow+'0' number = number mod tenPow end repeat display lastdig+'0' match any, trailer display trailer end match end macro and testing code Code: pos = 0 neg = 0 data = -11 extract_components data,pos,neg dispDec data display " in BCBTD form " dispBin pos display ":" dispBin neg display 13,10 algorithm itself working for any number but displays(dispDec) operate only small numbers. |
|||
|
18 May 2019, 12:39 |
|
|
guignol 18 May 2019, 15:28
It should be
positive, negative & neither |
|||
|
18 May 2019, 15:28 |
|
|
ProMiNick 20 May 2019, 00:09
I used storage format of ternary on binary HDD is:
positive and negative components are formed in blocks by 9 bytes and alternate; if file end tryte is not on the border of such blocks - special errorneus BCBTD (111111111:000000001) used as marker, all followed BCBTDs in block are 111111111:000000000. I don`t realize file end because of error in previous step - producing BCBTD blocks. tryed to make ternary directives to produce data Code: ternary?:: virtual at 0 positives:: db FILE_SIZE dup ? end virtual virtual at 0 negatives:: db FILE_SIZE dup ? end virtual macro extract_components value,outpos:0,outneg:0,size:0 local Number,Carry,Digit,?topos if value Number=value if Number<0 ?topos = -1 Number = -Number else ?topos = 1 end if Carry=0 while Number if size&size*9<% err value couldn`t fit end if Digit = Carry + Number mod 3 Number = Number / 3 if Digit < 2 Carry = 0 else Digit = Digit - 3 Carry = 1 end if if Digit = ?topos outpos = outpos or 1 shl (%-1) else if Digit = -?topos outneg = outneg or 1 shl (%-1) end if if ~Number if Carry = ?topos outpos = outpos or 1 shl % else if Carry = -?topos outneg = outneg or 1 shl % end if end if end while end if end macro ;__3^9 = 19683 macro __tryte_seq value,size local v,pos,neg,block,idx v = value pos = 0 neg = 0 extract_components v,pos,neg,size repeat size block = (($+%-1)/8)*9 idx = ($+%-1) mod 8 load H:word from positives:block+idx H = (H and $E0 shl idx) or pos shl idx store H:word from positives:block+idx load H:word from negatives:block+idx H = (H and $E0 shl idx) or neg shl idx store H:word from negatives:block+idx end repeat repeat size db 0 end repeat end macro macro tryte value __tryte_seq value,1 end macro macro tryade value __tryte_seq value,3 end macro macro vector value __tryte_seq value,9 end macro macro trivector value __tryte_seq value,27 end macro macro dt? definitions& iterate value,definitions match ?, value db ? else match n =dup? ?, value db n dup ? else match n =dup? (?), value db n dup ? else match n =dup? v, value repeat n tryte v end repeat else tryte value end match end iterate end macro struc dt? definitions& label . : byte iterate value,definitions match ?, value db ? else match n =dup? ?, value db n dup ? else match n =dup? (?), value db n dup ? else match n =dup? v, value repeat n tryte v end repeat else tryte value end match end iterate end macro macro dtd? definitions& iterate value,definitions match ?, value db 3 dup ? else match n =dup? ?, value db (n)*3 dup ? else match n =dup? (?), value db (n)*3 dup ? else match n =dup? v, value repeat n tryade v end repeat else tryade value end match end iterate end macro struc dtd? definitions& label . : ;byte*3 iterate value,definitions match ?, value db 3 dup ? else match n =dup? ?, value db (n)*3 dup ? else match n =dup? (?), value db (n)*3 dup ? else match n =dup? v, value repeat n tryade v end repeat else tryade value end match end iterate end macro macro dv? definitions& iterate value,definitions match ?, value db 9 dup ? else match n =dup? ?, value db (n)*9 dup ? else match n =dup? (?), value db (n)*9 dup ? else match n =dup? v, value repeat n vector v end repeat else vector value end match end iterate end macro struc dv? definitions& label . : ;byte*9 iterate value,definitions match ?, value db 9 dup ? else match n =dup? ?, value db (n)*9 dup ? else match n =dup? (?), value db (n)*9 dup ? else match n =dup? v, value repeat n vector v end repeat else vector value end match end iterate end macro macro dtv? definitions& iterate value,definitions match ?, value db 27 dup ? else match n =dup? ?, value db (n)*27 dup ? else match n =dup? (?), value db (n)*27 dup ? else match n =dup? v, value repeat n trivector v end repeat else trivector value end match end iterate end macro struc dtv? definitions& label . : ;byte*27 iterate value,definitions match ?, value db 27 dup ? else match n =dup? ?, value db (n)*27 dup ? else match n =dup? (?), value db (n)*27 dup ? else match n =dup? v, value repeat n trivector v end repeat else trivector value end match end iterate end macro postpone FILE_SIZE := (($+7)/8)*9 end virtual virtual as "positives" load H:$-$$ from 0 end virtual db H virtual as "negatives" load H:$-$$ from 0 end virtual db H end postpone virtual at 0 ;end header dt -5 dtv 7,600 |
|||
|
20 May 2019, 00:09 |
|
< Last Thread | Next Thread > |
Forum Rules:
|