Троичные вычисления на языке программирования Golang

[askfind]

Пришла идея как реализовать троичные вычисления тритов на языке программирования Golang:

Пример main.go

Code: Select all

package main

import (
"fmt"
)

func main() {

var trit1 interface{}
var tryte [6]interface{}

fmt.Println("\nt1: trit = NIL ")
trit1 = nil
fmt.Printf("trit1 == nil : %v \n", trit1 == nil)
fmt.Printf("trit1 == true : %v \n", trit1 == true)
fmt.Printf("trit1 == false : %v \n", trit1 == false)

fmt.Println("\nt2: trit = TRUE ")
trit1 = true
fmt.Printf("trit1 == nil : %v \n", trit1 == nil)
fmt.Printf("trit1 == true : %v \n", trit1 == true)
fmt.Printf("trit1 == false : %v \n", trit1 == false)

fmt.Println("\nt3: trit = FALSE ")
trit1 = false
fmt.Printf("trit1 == nil : %v \n", trit1 == nil)
fmt.Printf("trit1 == true : %v \n", trit1 == true)
fmt.Printf("trit1 == false : %v \n", trit1 == false)

fmt.Println("\nt4: tryte[6]")
fmt.Printf("tryte[6] = %v \n", tryte)

fmt.Println("\nt5: tryte[6]")
tryte[0] = true
tryte[1] = false
fmt.Printf("tryte[6] = %v \n", tryte)
}

Проверить код можно здесь https://play.golang.org/

Terminal print:

Code: Select all

t1: trit = NIL 
trit1 == nil : true 
trit1 == true : false 
trit1 == false : false 

t2: trit = TRUE 
trit1 == nil : false 
trit1 == true : true 
trit1 == false : false 

t3: trit = FALSE 
trit1 == nil : false 
trit1 == true : false 
trit1 == false : true 

t4: tryte[6]
tryte[6] = [<nil> <nil> <nil> <nil> <nil> <nil>] 

t5: tryte[6]
tryte[6] = [true false <nil> <nil> <nil> <nil>] 

[askfind]

Реализовал на языке golang объявление троичных типов данных
и сумматор с переносом.

Code: Select all

Таб.1 Алфавит троичной симметричной системы счисления
Символы       |   -     |  0    |  +    |
Числа            |  -1    |   0   |   1   |
Логика           | false |  nil  | true |

Выполнил тест суммирования:

Code: Select all

t8: add_t(...)
add_t( -1 + -1) => true, false 
add_t( -1 +  0) => false, <nil> 
add_t( -1 +  1) => <nil>, <nil> 
add_t(  0 + -1) => false, <nil> 
add_t(  0 +  0) => <nil>, <nil> 
add_t(  0 +  1) => true, <nil> 
add_t(  1 + -1) => <nil>, <nil> 
add_t(  1 +  0) => true, <nil> 
add_t(  1 +  1) => false, true 

Запуск main.go в режиме интерпретации:

Code: Select all

>$ go run main.go

Можно собрать быстрое бинарное приложение с троичными данными возможна для многих операционных систем.

1) Например для операционной системы embeded linux на ARM Sama5d36

Code: Select all

>$ GOOS=linux GOARCH=arm GOARM=7  go build main.go

>$ file main
main: ELF 32-bit LSB executable, ARM, EABI5 version 1 (SYSV), statically linked, Go BuildID=..., not stripped

2) Для операционной системы linux x86_64

Code: Select all

>$ GOOS=linux GOARCH=amd64  go build main.go

>$ file main
main: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), statically linked, Go BuildID=..., not stripped

3) Для операционной системы windows x86_64

Code: Select all

>$ GOOS=windows GOARCH=amd64  go build main.go

>$ file main
main: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), statically linked, Go BuildID=..., not stripped

[askfind]

Создал проект "Троичная симметричная арифметика" на языке GO

Ссылка: https://github.com/askfind/goTernaryArithmetic.git

Новости:
- Добавлена функция троичного умножения mul_t

ТЕСТ

Code: Select all

t9: mul_t(...) --------
mul_t( -1 * -1) => true 
mul_t( -1 *  0) => <nil> 
mul_t( -1 *  1) => false 
mul_t(  0 * -1) => <nil> 
mul_t(  0 *  0) => <nil> 
mul_t(  0 *  1) => <nil> 
mul_t(  1 * -1) => false 
mul_t(  1 *  0) => <nil> 
mul_t(  1 *  1) => true 

[askfind]

Полный троичный сумматор на языке Golang

Ссылка: https://github.com/askfind/goTernaryArithmetic.git

// Полный сумматор двух тритов с переносом
func add_full_t(a trit, b trit, incarry trit) (c trit, outcarry trit) {
s, sc := add_half_t(a, b)
d, dc := add_half_t(s, incarry)
ss, _ := add_half_t(sc, dc)
return d, ss
}

Запуск теста:

Code: Select all

$ go test  -run ^TestAddFullTrits

Test ADD FULL TRITS  add_full_t(...):
add_full_t( -1 + -1 + -1) => <nil>, false 
add_full_t( -1 + 0 + -1) => true, false 
add_full_t( -1 + 1 + -1) => false, <nil> 
add_full_t( -1 + 1 + 1) => true, <nil> 
add_full_t(  0 + 1 +  1) => false, true 
add_full_t(  1 + 1 +  1) => <nil>, true 

Сумма тритов с переносом:

Code: Select all

$ go run goTernaryArithmetic.go 

Run funcs ---------------------
a=0, b=1, c=-1, carry=1   
add_full_t( 0, 1, 1 ) = -1,1 
-------------------------------

Проверим производительность полного сумматора:

Code: Select all

go test -benchmem -run= -bench BenchmarkCalculate

goos: linux
goarch: amd64
BenchmarkCalculate-8   	221751032	         5.54 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	_goTernaryArithmetic	1.785s

[Shaos]

Отделил сообщения про Golang в новую тему

[askfind]

Проверка производительности полного сумматора тритов на ARM (Atmel SAMA5D36: F=536 MHz)

Code: Select all

>$ go test -benchmem -run= -bench BenchmarkCalculate

goos: linux
goarch: arm
BenchmarkCalculate 	20000000	       108 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	_/mnt/mmcblk1p3/Apps/My/goTernaryArithmetic	2.366s

[askfind]

Новости проекта: https://github.com/askfind/goTernaryArithmetic

Добавлены:
- новый тип данных TRYTE.
- Операция сдвига тритов в трайте.
//
// Операция сдвига тритов
//
// Параметр:
// if(d > 0) then "Вправо"
// if(d == 0) then "Нет сдвига"
// if(d < 0) then "Влево"
// Возврат: Троичное число
//
- Функция измерение порядка тритов в трайте
- Функция печати трайта как число со знаком Tryte[]=[0][1][2][3][4][5]=[-1 0 1 0 0 -1]
- Функция печати трайта как символ "-","0","+" Tryte[]=[0][1][2][3][4][5]=[- 0 + 0 0 -]

Code: Select all

Run funcs ---------------------
- calculate trit  --------------
a=0, b=1, c=-1, carry=1   
add_full_t( 0, 1, 1 ) = -1,1 
- calculate tryte  --------------
x = [0 -1 1 0 -1 1] 
x = [0 - + 0 - +] 
shift_ts( x, -5 ) = [1 0 0 0 0 0] 
shift_ts( x, -5 ) = [+ 0 0 0 0 0] 
x = [-1 0 0 0 0 0] 
x = [- 0 0 0 0 0] 
shift_ts( x, 5 ) = [0 0 0 0 0 -1] 
shift_ts( x, 5 ) = [0 0 0 0 0 -] 
--------------------------------

Производительность троичных операций

Code: Select all

$ go test -bench=.

goos: linux
goarch: amd64
BenchmarkPow3-8                 75324468                15.8 ns/op
BenchmarkShift_ts-8             20947730                59.2 ns/op
BenchmarkAdd_full_t-8           50879143                23.6 ns/op
BenchmarkMul_t-8                228886077                4.92 ns/op
PASS
ok 

[Shaos]

Надо проверить, а не быстрее ли будет просто с int-ами работать (-1, 0, +1), а не использовать <nil> как третье состояние - nil это же скорее исключительная ситуация, чем нормальная работа?

[askfind]

Надо проверить, а не быстрее ли будет просто с int-ами работать (-1, 0, +1), а не использовать <nil> как третье состояние - nil это же скорее исключительная ситуация, чем нормальная работа?

Здравия!

Добавил полный троичный сумматор и в качестве трита как int данное.

Производительность sum_t

Code: Select all

goos: linux
goarch: amd64
BenchmarkSum_t-8   	236201059	         4.88 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	

Исследовал разные реализации тритов и трайтов в эмуляторе "Setun-1958" с целью производительности операций в ARM-архитектуре и максимально близко к инструкциям микроконтроллера:

(Вариант 1) BITS
'00' '10' '01' '11'

Трит:
typedef uint32_t trit;

Слово из тритов:
typedef struct trs {
int w;
int l;
uint64_t trit; // для 18 трит * 2 = 36 бит для регистра "Setun"
} trs_t;

(Вариант 2) INT
/* Тип данных троичное целое число */
typedef struct trin {
int n;
int trit[SIZE_WORD_EMUL];
} trit_t;

Посмотрел генерацию кода в ассемблер из С.

Медленная реализация эмуляции работы со словами регистров "Setun-1958":
1,5,9,18 тритов.


Идею использовать "false,nil,true" подглядел здесь на форуме.

Code: Select all

// Таб.1 Алфавит троичной симметричной системы счисления
// +--------------------------+-------+-------+-------+
// | Числа                    |  -1   |   0   |   1   |
// +--------------------------+-------+-------+-------+
// | Символы (вар.1)          |   -   |	  0   |	  +   |
// +--------------------------+-------+-------+-------+
// | Символы (вар.2)          |   v   |	  0   |	  ^   |
// +--------------------------+-------+-------+-------+
// | Символы (вар.3)          |   N   |	  O   |	  P   |
// +--------------------------+-------+-------+-------+
// | Символы (вар.4)          |   0   |	  i   |	  1   |
// +--------------------------+-------+-------+-------+
// | Логика                       | false |  nil  | true  |
// +--------------------------+-------+-------+-------+

Многие микроконтроллеры имеют битовые операции установки, очистки бита. Условный переход посотоянию бита.

Быстрый код операций на обычном двоичном процессоре, на мой взгляд, можно обеспечить так

TRYTE[6]
byte1 [5][4][3][2][1][0]
byte0 [5][4][3][2][1][0]

TRIT0 = {byte1[0],byte0[0]}

byte1[0] = {false,true}
byte1[0] = {false,true}

if ( byte0[0] == 0 ) {
TRIT= NIL
}
else {
if (byte1[0] == 0 )
{
TRIT = -1
}
else
{
TRIT = 1
}
}

- Упрощается троичный сдвиг, сдвигая разряды byte1, byte0 командами двоичного процессора.
- Упрощается умножение byte0[0] маскирует разряды

Например, для контроллера AVR

CBR Rd, K Очистка разрядов регистра Rd ← Rd and (0FFH – K) Z, N, V
SBR Rd, K Установка разрядов регистра Rd ← Rd or K Z, N, V

LSL Rd Логический сдвиг влево Rd(i+1) ← Rd(i), Rd(0) ← 0, C ← Rd(7) Z, C, N, V
LSR Rd Логический сдвиг вправо Rd(i) ← Rd(i+1), Rd(7) ← 0, C ← Rd(0) Z, C, N, V
ROL Rd Сдвиг влево через перенос Rd(i+1) ← Rd(i), Rd(0) ← C, C ← Rd(7) Z, C, N, V
ROR Rd Сдвиг вправо через перенос Rd(i) ← Rd(i+1), Rd(7) ← C, C ← Rd(0) Z, C, N, V

SBRC Rd, K Пропустить следующую команду если бит в регистре очищен Если Rd[K] = 0 —
SBRS Rd, K Пропустить следующую команду если бит в регистре установлен Если Rd[K] = 1 —

Например, в ARM Cortex STM32
реализован способ управлять битами памяти, портов с использованием memory bitband

https://blablacode.ru/mikrokontrollery/455

Как работает Bit Banding?
Bit Banding – термин, который использует ARM для обозначения механизма доступного в Cortex M3 and M4 ядрах. Если говорить просто, то в устройстве берется участок памяти и каждый бит этого участка связывается со словом в другом участке памяти.
«Магия» Bit Banding в том, что при записи слов данных во второй участок, изменяются биты в первом. Операция установки, снятия бита занимает одну машинную инструкцию, что делает невозможным потерю данных. Т.е. такой подход обеспечивает атомарный доступ к памяти.

[askfind]

Представление в памяти поля тритов и функция get_trit() для ARM

Число из 32-тритов:
trs[32]
uint32_t t1;
uint32_t t0;

Code: Select all

Реализация функции get_trit() на C для ARM

Использовать объявление для компилятора register, чтобы получить бинарные операции в ассемблере ARM/

Реализация функции чтение трита:

Code: Select all

int get_trit(register uint32_t t1,register uint32_t t0,register uint8_t p ) {
        int trit;
        if ((t0 & (1<<0)) == 0)  {
                trit = 0;
        }
        else {
                if ((t1 & (1<<0)) == 0) {
                        trit = -1;
                }
                else {
                        trit = 1;
                }
        }
        return trit;
}

Фрагмент листинга на ассемблере ARM

Code: Select all

Команда: arm-none-eabi-gcc -S main.c для получения листинга ассемблера: 

Фрагмент функции:
get_trit:
	@ Function supports interworking.
	@ args = 0, pretend = 0, frame = 8
	@ frame_needed = 1, uses_anonymous_args = 0
	@ link register save eliminated.
	str	fp, [sp, #-4]!
	add	fp, sp, #0
	sub	sp, sp, #12
	mov	r3, r1
	mov	ip, r2
	mov	r1, ip
	mov	r2, #1
	lsl	r2, r2, r1
	and	r3, r3, r2
	cmp	r3, #0
	bne	.L2
	mov	r3, #0
	str	r3, [fp, #-8]
	b	.L3

Вывод в консоль работы приложения:

Code: Select all

Test print trit:
 trit=-1
 trit= 0
 trit= 1
Shift to the left {t1,t0}<<= 2:
 shift trit= 1

ВЫВОД:
- Компилятор генерирует оптимальные инструкции для микроконтроллера ARM.
- Компактный код реализации функции работы с тритом {-1,0.1}.
- Очень быстрая и оптимальная операции сдвига вправо и влево троичного числа для микроконтроллера ARM.

Из работы ЗАМЕТКИ О ТРОИЧНОЙ ЦИФРОВОЙ ТЕХНИКЕ - ЧАСТЬ 2 Н. П. Брусенцов
"...

На первый взгляд описанная архитектура не отличается от архитектуры двоичных одноаккумуляторных машин: те же регистры, те же операции. Однако при внимательном рассмотрении выявляются следующие принципиальные и
важные для практики особенности.

1. Числа всех типов представлены единым натуральным кодом. В двоичных машинах для представления чисел разных типов и даже разного назначения приходится применять различный код, например: числа с фиксированной запятой представляют обычно дополнительным или обратным кодом, мантиссы чисел с плавающей запятой - прямым кодом, порядки - кодом с избытком,
адреса памяти - натуральным двоичным кодом.

2. Операции определены над операндами, длина которых варьируется и может быть неодинаковой у первого и второго операнда. При этом не требуется никаких усложнений операционного устройства, ни вспомогательных команд в роде двоичной команды "расширения знака".

3. При усечении слова, например в случае присваивания длинного значения короткому регистру, автоматически получается наилучшее при данной
укороченной длине представление первоначального значения, и вместе с тем сохраняемая часть слова копируется неизменной. В двоичной машине
соответствующие возможности с известными оговорками можно обеспечить, лишь предусмотрев два варианта операций - с округлением и без округления.

4. Единственная операция сдвига выполняет функции всех двоичных операций сдвига - логического, арифметического, с округлением и без округления, причем выполняет безукоризненно, чего нельзя сказать, например, об операции двоичного арифметического сдвига [6].

5. Знак числа в соответствии с общепринятой математической трактовкой этого понятия представлен трехзначной функцией, и разбиение чисел по знаку производится на положительные, отрицательные и равные нулю в противоположность сбивающей с толку двоичной традиции двузначного знака и отнесения нуля к положительным числам.

6. Интервал значения мантиссы нормализованного числа - от 0,5 до 1,5 по абсолютной величине - характеризуется значительно лучшей устойчивостью по сравнению с используемыми в двоичных машинах интервалами 0,5 - 1,0 и 1,0 -2,0.

Эти и некоторые другие особенности троичной архитектуры обусловили математическое совершенство, компактность и простоту реализации набора команд "Сетуни", а главное, естественность, легкость понимания и применения машины пользователями.

Буду внедрять именно такой способ представления тритов в памяти контроллера и переделывать исходный эмулятора троичного компьютера "Setun-1958" - https://github.com/askfind/Emulator-Setun-1958

[askfind]

Реализовал функцию get_trit() на Golang

Поразрядные операции на Golang

Поразрядные операции также проводятся только над разрядами целочисленных операндов:

& : поразрядная конъюнкция (операция И или поразрядное умножение). Возвращает 1, если оба из соответствующих разрядов обоих чисел равны 1. Возвращает 0, если разряд хотя бы одного числа равен 0

| : поразрядная дизъюнкция (операция ИЛИ или поразрядное сложение). Возвращает 1, если хотя бы один из соответствующих разрядов обоих чисел равен 1

^ : поразрядное исключающее ИЛИ. Возвращает 1, если только один из соответствующих разрядов обоих чисел равен 1

&^ : сброс бита (И НЕ). В выражении z = x &^ y каждый бит z равен 0, если соответствующий бит y равен
Если бит в y равен 0, то берется значение соответствующего бита из x.

Code: Select all

/
// Реализация чтение трита
//
func get_trit(t1 uint32, t0 uint32, p uint8) int {
	var trit int
	if (t0 & (1 << p)) == 0 {
		trit = 0
	} else {
		if (t1 & (1 << p)) == 0 {
			trit = -1
		} else {
			trit = 1
		}
	}
	return trit
}

Вывод теста чтения трита:

Test print trt:
trt=-1
trt= 0
trt= 1
Shift to the left {t1,t0}<<= 2:
shift trt= 1

Code: Select all

goos: linux
goarch: amd64
BenchmarkGet_Trit-8   	1000000000	         0.396 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	_goTernaryArithmetic	0.458s

[Shaos]

чото нифига непонятно по бенчмаркам - что быстрее то? с интом или с нилом?

[askfind]

чото нифига непонятно по бенчмаркам - что быстрее то? с интом или с нилом?

Для железа: linux, x86_64, Intel(R) Core(TM) i7-2630QM CPU @ 2.00GHz

1) {FALSE,NIL,TRUE} - версия 1 вычисление полного сумматора тритов
BenchmarkAdd_full_t-8 41466112 24.6 ns/op

2) {-1,0,1} - версия 2 вычисление полного сумматора тритов
BenchmarkSum_t-8 216968636 5.39 ns/op 0 B/op

Code: Select all

// Троичное сложение двух тритов с переносом
// (Для измерения производительности операций int)
func sum_t(a int, b int, p0 int) (int, int) {
	s := a + b + p0
	switch s {
	case -3:
		return 0, 1
		break
	case -2:
		return 1, -1
		break
	case -1:
		return -1, 0
		break
	case 0:
		return 0, 0
		break
	case 1:
		return 1, 0
		break
	case 2:
		return -1, 1
		break
	case 3:
		return 0, 1
		break
	default:
		return 0, 0
		break
	}
	return 0, 0
}

ВЫВОД
- Функция полного сумматора тритов с переносом с типами данных INT работает быстрее в 5 раз.

[Shaos]

Ну т.е. как я и предполагал - с интеджерами быстрее

[askfind]

Ну т.е. как я и предполагал - с интеджерами быстрее

Для полного сумматора - да. Согласен.

Продолжаю проверять и другие реализации функций тритов и троичных слов.

Теперь проверяю производительность функций операций с троичными словами длиной 32-трита.

• trs2int( tr[32], 31 ) - чтение трита : Benchmark_trs2int 0.356 ns/op
  int2trs( tr[32], 31,-1) - запись трита : Benchmark_int2trs 0.363 ns/op
  sgn_trs( tr[32] ) - определение знака числа 32-трита : Benchmark_sgn_trs 61.9 ns/op
  shift_trs(tr trs, d int8) - троичный сдвиг 32-тритов влево и вправо : Benchmark_shift_trs 0.361 ns/op
  add_trs(x trs, y trs) - троичный сумматор чисел 32 трита : Benchmark_add_trs 434 ns/op
  sub_trs(x trs, y trs) - троичное вычитание чисел 32 трита : Benchmark_add_trs 429 ns/op