flat assembler
Message board for the users of flat assembler.

 Index > Main > math question about balanced ternary representation
Author
ProMiNick

Joined: 24 Mar 2012
Posts: 797
Location: Russian Federation, Sochi
ProMiNick 17 May 2019, 13:39
we have a numer

Code:
`+"a big number something like this or bigger"    `

I interest in extraction of positive & negative components of it in form of balanced ternary representation?

algorithm:
1. extract sign from number
2. find highest setted bit(trit) in positive(if sign +) or negative (if sign -) component of binary representation of balanced ternary number - finding is successfull if difference between (our number) and (3 in power of position of that bit) is less than half of (3 in power of position of that bit).
3. decrease our number with 3 in power of bit founded in step 2
4. if our number not null back to step 1

Question 1 - is algorithm correct? looks like yes, but may be I missed something.
Question 2 - how to realize that extraction in fasmg?
Code:
`macro extract_components value,size:0,outpos:0,outneg:0    `

if size is set first tested bit is (9*size)th otherway initial searching of highest bit started from least significant bit (or there are more effective way?

_________________
I don`t like to refer by "you" to one person.
My soul requires acronim "thou" instead.
17 May 2019, 13:39
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20250
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

Joined: 24 Mar 2012
Posts: 797
Location: Russian Federation, Sochi
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
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20250
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

Joined: 24 Mar 2012
Posts: 797
Location: Russian Federation, Sochi
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
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20250
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

Joined: 24 Mar 2012
Posts: 797
Location: Russian Federation, Sochi
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
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20250
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

Joined: 24 Mar 2012
Posts: 797
Location: Russian Federation, Sochi
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
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20250
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

Joined: 24 Mar 2012
Posts: 797
Location: Russian Federation, Sochi
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

Joined: 24 Mar 2012
Posts: 797
Location: Russian Federation, Sochi
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

Joined: 16 Jun 2003
Posts: 8347
Location: Kraków, Poland
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
BalancedTernary = BalancedTernary bswap lengthof BalancedTernary
end virtual

display BalancedTernary    ```
17 May 2019, 23:10
ProMiNick

Joined: 24 Mar 2012
Posts: 797
Location: Russian Federation, Sochi
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
end match
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

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
end match
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

Joined: 06 Dec 2008
Posts: 763
guignol 18 May 2019, 15:28
It should be
positive, negative & neither
18 May 2019, 15:28
ProMiNick

Joined: 24 Mar 2012
Posts: 797
Location: Russian Federation, Sochi
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
H = (H and \$E0 shl idx) or pos shl idx
store H:word from positives: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

__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
end repeat
else
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
end repeat
else
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"
end virtual
db H
virtual as "negatives"
end virtual
db H
end postpone

virtual at 0

dt -5
dtv 7,600    ```
20 May 2019, 00:09
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum