nedoPC.org - View topic - Троичные вычисления на языке программирования Golang

Atom Feed | View unanswered posts | View active topics

It is currently 18 Apr 2024 06:34

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

Moderator: haqreu

Page 1 of 2

[ 22 posts ]

Go to page 1, 2 Next

Previous topic | Next topic

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

Author

Message

askfind

Doomed

Joined: 04 Jan 2016 09:15
Posts: 656
Location: Russia, S.- Peterburg

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

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

Пример main.go


	Code: 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: 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>]

_________________
"Ученье свет, а неученье — тьма. Дело мастера боится, и коль крестьянин не умеет сохою владеть — хлеб не родится." (С)

23 Aug 2021 01:14

askfind

Doomed

Joined: 04 Jan 2016 09:15
Posts: 656
Location: Russia, S.- Peterburg

Re: Программирование с помощью троичной логики

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


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

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


	Code: 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: >$ go run main.go

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

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


	Code: >$ 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: >$ 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: >$ 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


	Attachments: main.zip [1.06 KiB] Downloaded 275 times

27 Aug 2021 07:16

askfind

Doomed

Joined: 04 Jan 2016 09:15
Posts: 656
Location: Russia, S.- Peterburg

Re: Программирование с помощью троичной логики

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

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

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

ТЕСТ


	Code: 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

28 Aug 2021 04:38

askfind

Doomed

Joined: 04 Jan 2016 09:15
Posts: 656
Location: Russia, S.- Peterburg

Re: Программирование с помощью троичной логики

Полный троичный сумматор на языке 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: $ 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: $ go run goTernaryArithmetic.go Run funcs --------------------- a=0, b=1, c=-1, carry=1 add_full_t( 0, 1, 1 ) = -1,1 -------------------------------

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


	Code: 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

Last edited by askfind on 30 Aug 2021 21:20, edited 1 time in total.

30 Aug 2021 12:49

Shaos

Admin

Joined: 08 Jan 2003 23:22
Posts: 22530
Location: Silicon Valley

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

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

_________________
:dj:

https://mastodon.social/@Shaos

30 Aug 2021 20:22

askfind

Doomed

Joined: 04 Jan 2016 09:15
Posts: 656
Location: Russia, S.- Peterburg

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

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


	Code: >$ 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

01 Sep 2021 03:44

askfind

Doomed

Joined: 04 Jan 2016 09:15
Posts: 656
Location: Russia, S.- Peterburg

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

Новости проекта: 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: 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: $ 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

01 Sep 2021 18:45

Shaos

Admin

Joined: 08 Jan 2003 23:22
Posts: 22530
Location: Silicon Valley

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

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

_________________
:dj:

https://mastodon.social/@Shaos

02 Sep 2021 13:09

askfind

Doomed

Joined: 04 Jan 2016 09:15
Posts: 656
Location: Russia, S.- Peterburg

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


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

Здравия!

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

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


	Code: 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: // Таб.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


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

02 Sep 2021 15:34

askfind

Doomed

Joined: 04 Jan 2016 09:15
Posts: 656
Location: Russia, S.- Peterburg

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

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

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


	Code:

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

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

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


	Code: 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: Команда: 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: Test print trit: trit=-1 trit= 0 trit= 1 Shift to the left {t1,t0}<<= 2: shift trit= 1

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


	Quote: Из работы ЗАМЕТКИ О ТРОИЧНОЙ ЦИФРОВОЙ ТЕХНИКЕ - ЧАСТЬ 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


	Attachments: slide-64.jpg [ 143.18 KiB \| Viewed 7494 times ] get_trit.zip [1.34 KiB] Downloaded 269 times

04 Sep 2021 03:15

askfind

Doomed

Joined: 04 Jan 2016 09:15
Posts: 656
Location: Russia, S.- Peterburg

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

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

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

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

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

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

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

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


	Code: / // Реализация чтение трита // 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 }

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


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


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

04 Sep 2021 04:08

Shaos

Admin

Joined: 08 Jan 2003 23:22
Posts: 22530
Location: Silicon Valley

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

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

_________________
:dj:

https://mastodon.social/@Shaos

04 Sep 2021 18:23

askfind

Doomed

Joined: 04 Jan 2016 09:15
Posts: 656
Location: Russia, S.- Peterburg

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


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

Для железа: 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: // Троичное сложение двух тритов с переносом // (Для измерения производительности операций 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 раз.

04 Sep 2021 20:48

Shaos

Admin

Joined: 08 Jan 2003 23:22
Posts: 22530
Location: Silicon Valley

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

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

_________________
:dj:

https://mastodon.social/@Shaos

05 Sep 2021 22:19

askfind

Doomed

Joined: 04 Jan 2016 09:15
Posts: 656
Location: Russia, S.- Peterburg

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


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

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

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

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

trs2int( tr[32], 31 )

0.356 ns/op

int2trs( tr[32], 31,-1)

0.363 ns/op

sgn_trs( tr[32] )

61.9 ns/op

shift_trs(tr trs, d int8)

0.361 ns/op

add_trs(x trs, y trs)

434 ns/op

sub_trs(x trs, y trs)

429 ns/op

05 Sep 2021 22:59

Page 1 of 2

[ 22 posts ]

Go to page 1, 2 Next

Who is online

Users browsing this forum: No registered users and 12 guests

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 post attachments in this forum

Jump to: