flat assembler
Message board for the users of flat assembler.

flat assembler > Heap > math question about balanced ternary representation

Author
Thread Post new topic Reply to topic
ProMiNick



Joined: 24 Mar 2012
Posts: 316
Location: Russian Federation, Sochi
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.
Post 17 May 2019, 13:39
View user's profile Send private message Send e-mail Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 16628
Location: In your JS exploiting you and your system
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.
Post 17 May 2019, 14:23
View user's profile Send private message Visit poster's website Reply with quote
ProMiNick



Joined: 24 Mar 2012
Posts: 316
Location: Russian Federation, Sochi
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.
Post 17 May 2019, 16:19
View user's profile Send private message Send e-mail Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 16628
Location: In your JS exploiting you and your system
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.
Post 17 May 2019, 16:26
View user's profile Send private message Visit poster's website Reply with quote
ProMiNick



Joined: 24 Mar 2012
Posts: 316
Location: Russian Federation, Sochi
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,
Post 17 May 2019, 18:24
View user's profile Send private message Send e-mail Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 16628
Location: In your JS exploiting you and your system
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.
Post 17 May 2019, 18:28
View user's profile Send private message Visit poster's website Reply with quote
ProMiNick



Joined: 24 Mar 2012
Posts: 316
Location: Russian Federation, Sochi
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.
Post 17 May 2019, 18:45
View user's profile Send private message Send e-mail Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 16628
Location: In your JS exploiting you and your system
What are you having trouble with? The conversion? The storage? The fasmg code?
Post 17 May 2019, 19:10
View user's profile Send private message Visit poster's website Reply with quote
ProMiNick



Joined: 24 Mar 2012
Posts: 316
Location: Russian Federation, Sochi
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.
Post 17 May 2019, 21:04
View user's profile Send private message Send e-mail Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 16628
Location: In your JS exploiting you and your system
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.
Post 17 May 2019, 21:06
View user's profile Send private message Visit poster's website Reply with quote
ProMiNick



Joined: 24 Mar 2012
Posts: 316
Location: Russian Federation, Sochi
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    
Post 17 May 2019, 22:02
View user's profile Send private message Send e-mail Reply with quote
ProMiNick



Joined: 24 Mar 2012
Posts: 316
Location: Russian Federation, Sochi
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.
Post 17 May 2019, 23:05
View user's profile Send private message Send e-mail Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 7289
Location: Kraków, Poland
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    
Post 17 May 2019, 23:10
View user's profile Send private message Visit poster's website Reply with quote
ProMiNick



Joined: 24 Mar 2012
Posts: 316
Location: Russian Federation, Sochi
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.
Post 18 May 2019, 12:39
View user's profile Send private message Send e-mail Reply with quote
guignol



Joined: 06 Dec 2008
Posts: 540
Location: Did I forgot to take off the kettle again?
It should be
positive, negative & neither
Post 18 May 2019, 15:28
View user's profile Send private message Reply with quote
ProMiNick



Joined: 24 Mar 2012
Posts: 316
Location: Russian Federation, Sochi
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    
Post 20 May 2019, 00:09
View user's profile Send private message Send e-mail Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You can attach files in this forum
You can download files in this forum


Copyright © 1999-2019, Tomasz Grysztar.

Powered by rwasa.