Никаких обид, интересный вопрос. С радостью отвечу. Начнём с примера который любезно сгенерил chat gpt.
Правда, я совсем не уверен, что этот ваш «троичный поиск» эффективнее двоичного, ибо если был бы, его бы давно использовали. Но что-то подобный алгоритм не популярен.
Сомневаетесь, а зря (если я, конечно, дальше нигде не ошибся). В теории безусловно будет быстрее, в первую очередь за счет сокращения второй и третьей итерации и возможности обработать большую часть массива в первой и необходимом меньшем количестве операций по сравнению. Это происходит за счет уменьшения количества шагов, необходимых для нахождения элемента, так как на каждом шаге исключается больше неподходящих элементов:
В двоичном поиске, если у нас есть массив размером ( n ), то максимальное количество сравнений, которое потребуется сделать, составляет ( \log_2{n} ). В троичном поиске, это количество уменьшается до ( \log_3{n} ), что демонстрирует уменьшение количества шагов, так как ( \log_3{n} < \log_2{n} ) для любого ( n > 1 ).
Предположим существует упорядоченный массив из 27 элементов, если мы используем двоичный поиск потребуется до 5 сравнений, так как ( \log_2{27} ≈ 4.75 ), в троичном достаточно 3-х, так как ( \log_3{27} = 3 ).
Концепция троичных компьютеров (как и тетрарная система счисления) не популярна по целому ряду причин, которые я описал в статье. В первую очередь троичная логика не привычна и не типична, а создание тетраных компьютеров ограничено ресурсоёмкостью создания элементной базы и ПО для них - это время деньги, а прирост производительности может не окупить затрат. Я отнюдь не утверждаю, что всем совершенно необходимо перейти на троичные компы за десять лет и забыть про традиционные двоичные, но тема имеет право на существование.
Подозреваю, что если их спросить: «Ну, а чем, чем оно лучше?»
Оспаривать то, что у потенциальных троичных систем есть очевидные математические преимущества, на мой взгляд абсурдно. В вычислениях больше теоретическое преимущество троичной системе даёт радиксная экономия ( R ) для системы счисления с основанием ( b ) и ( d ) цифрами - это отношение количества цифр ( d ) к логарифму по основанию ( b ) от ( d ):
[ R = \frac{d}{\log_b{d}} ]
Так у тетрарной системы, где b = 3, [ R = \frac{d}{\log_3{d}} ] , логарифмическая функция (\log_b{d} ) растет медленнее, чем линейная функция d. Радиксная экономия достигает минимума при b = e (основание натурального логарифма). ( e ) - не является целым числом и ближайшим к нему целым числом является 3.
Для двоичной системы( b = 2 ), [ R_{binary} = \frac{d}{\log_2{d}} ], значение ( R ) будет выше, чем для троичной системы. Соответственно в двоичной системе необходимо больше цифр для представления того же количества информации.
Очевидна более высокая информационная ёмкость, т.к. троичная система счисления даёт возможность хранить больше информации на единицу памяти (чисто математически), трит может представлять три состояния (-1, 0, +1), а бит представляет только два (0, 1).
Также симметричное представление чисел относительно нуля в уравновешенной тетрарной системе упрощает алгоритмы поиска и сравнения, так как числа можно сравнивать без необходимости отдельно учитывать отрицательные и положительные, например: В троичной системе, мы можем представить отрицательные числа, просто заменив их на отрицательный эквивалент. Например, если у нас есть троичное число a +1-10 (a==4), его отрицательная версия будет -1+10 (a==-4), итог - нет необходимости дополнительных шагов.
В двоичной системе несколько сложнее, инверсия числа включает инвертирование каждого бита (0 становится 1, и наоборот) и последующее добавление единицы к результату. Представим двоичное число a 0101 (a==5). Инвертирование каждого бита даёт нам 1010, добавляем 1 и получаем 1011(a==-5), появляется дополнительный шаг.
Это не всё, но это аргументационная база обоснований большей математической эффективности тетрарной системы счисления для использования в вычислительной технике. Полагаю, что именно по этим причинам Дональд Кнут считал, что "Возможно, самая красивая система счисления — это сбалансированная троичная"
выдержку из какой-то статьи
Ага, из моей)
квантовыми компьютерами, потому что в теории они могут решать некоторые задачи кардинально быстрее, чем существующие компьютеры.
Ну как минимум сомножетили числа 15 при исполнении алгоритма Шора были найдены с использованием квантового компьютера. Факторизация числа 21, опять же. Эксперименты с квантовыми компьютерами проводятся всего 30 лет, очевидно этого не достаточно. Но тот же Google тратит миллионы на использование компьютеров D-Wave для получения выборок, на которые у классических компьютеров ушли бы сотни, если не тысячи лет. Тут вопрос стоимости эффективных решений и теоретической возможности создания универсального квантового компьютера. Тут я скорее квантовый оптимист, но понимаю, что эта история не будет быстрой.
Тут только вопрос о том каких транзисторов и каких устройств. Ну и цифра скромная, учитывая амбиции "догнать и перегнать". И, как я уже писал выше, речь про 1957-й год, когда "Сетунь" уже 2 года как разрабатывали и архитектура уже была создана.
Ну, собственно, о чём я и говорю. 2,7 млн - это не про то, что "транзисторов практически не было".
Ну так это в 1957-м, а не в 1955-м (когда начали разрабатывать "Сетунь"), это во первых, а во вторых это через 3 года после начала серийного производства транзисторов, причем речь про все типы транзисторов. И не факт, что все они были годны к использованию, речь шла о том, сколько всего было выпущено, нет данных сколько из них отбраковали и в каких режимах, при каких нагрузках они могли работать. Все авторы того времени сходятся в едином мнении, что транзисторов был катастрофический дефицит и что советские транзисторы первого поколения были редкостным дерьмом, до середины 1960-х.
Насколько я помню, как раз военка и космос обеспечивались всем необходимым в первую очередь, а вот ширпотреб уже подключался тогда, когда военка была удовлетворена.
Это верно. И полагаю, что начали выпускать как раз для военки и космоса, но получив то, что получили, решили использовать хотя бы ширпотребе ибо качество было катастрофическим. Об этом пишут все, кто тогда жил, ну кроме журналистов официальной советской прессы (доверять журналистам и не доверять инженерам, я полагаю, абсурдно).
Так что авторов Сетуни, вполне возможно, просто не устраивало качество
Думаю, что у авторов "Сетуни" просто небыло выбора.
Единственным известным примером использования троичной машины в оборонке является "Сетунь" с тем же наставником. Об этом говорил Брусенцов, вскользь в интервью, о том, что кого-то где-то обучали при помощи наставника. Предположительно, часть из серийных "Сетуней" ушли куда-то по оборонной линии, но это не точно, делаю вывод из того, что не все были использованы в ВУЗах и на производствах. Предполагаю, что речь также шла об использовании в учебных заведениях. Особенности программирования на троичных машинах не позволяли использовать их массово, что часто необходимо в оборонке. Также есть основания полагать, что если бы на эти компы был военный заказ и осознанные перспективы применения в оборонке, то их судьба сложилась бы иначе.
Для ширпотреб электроники они возможно были и годны, но и для военки, космоса и компьютеров - нет. Низкая термостабильность, большой разброс параметров. Главная проблема - советская культура производства. Вот вам цитата из «Основы радиолокационной техники. Часть II» (Военное издательство МО СССР, 1959) Е. А. Каткова и Г. С. Кромина:
«...электроды транзистора, дозируемые из проволоки вручную, графитовые кассеты, в которых производилась сборка и формирование pn-переходов, – эти операции требовали точности, …время процессов контролировалось секундомером. Всё это не способствовало высокому выходу годных кристаллов. Он и был поначалу от нуля до 2–3 %. Не способствовала высокому выходу и производственная обстановка. Вакуумная гигиена, к которой привыкла «Светлана», для производства полупроводниковых приборов была недостаточна. Это же относилось и к чистоте газов, воды, воздуха, атмосферы на рабочих местах… и к чистоте применяемых материалов, и к чистоте тары, и к чистоте полов и стен. Наши требования встречали непонимание. На каждом шагу руководители нового производства натыкались на искреннее возмущение служб завода: «Все вам даем, а вам все не то!» Не один месяц прошел, пока заводской коллектив усвоил и научился выполнять необычные, избыточные, как тогда казалось, требования новорожденного цеха».
И ещё одна Я. А. Федотова, Ю. В. Шмарцева из книги «Транзисторы» (Советское Радио, 1960):
Наш первый прибор вышел довольно нескладным, поскольку, работая среди вакуумщиков во Фрязино, мы мыслили себе конструкции как-то иначе. Наши первые НИРовские образцы тоже были сделаны на стеклянных ножках с вваренными выводами, и очень трудно было понять, как эту конструкцию герметизировать. Конструкторов у нас не было, как, впрочем, и никакого оборудования. Не удивительно, что первая конструкция приборов была очень примитивной, безо всякой сварки. Была только закатка, и делать их было очень трудно...
К слову о количестве, в 1957 выпуск транзисторов в СССР составлял 2,7 млн шт, в США - 28 миллионов. Превысить порог в 10 млн в год, в СССР смогли только в 1966 году.
П1 — первый советский серийный плоскостной транзистор, начало промышленного выпуска — 1955 год.
И тут же:
Выпускался на ленинградском заводе «Светлана» с 1955 до 1960 года. Первые выпуски имели обозначения КСВ-1, КСВ-2 и некоторые другие. Из-за сложностей в освоении совершенно новых для завода технологических процессов выход годной продукции в первые месяцы производства составлял всего 2-3 %.
Я нигде не писал, что в 55-м начали серийное производство. И да, понимали из чего будут делать. Транзисторов мало, лампы - не подходят. Нужна альтернатива, ферритдиодная ячейка Гутенмахера - подходящая альтернатива. Схемотехника проще, надёжность выше, стоимость ниже, проблем с производством в товарных количествах - нет. И да, планировали создать компьютер, который подходил бы для серии. И таки создали. И в серию пошел, но она была небольшой, стартовала фактически в 1962 году.
Легенда же. Ну или намеренная деза), тоже как вариант. В Британии к 1956 Metrovick 950 уже сделали. Между тем сомнительность легенды не отменяет того факта, что с транзисторами, в том числе с плоскостными, о которых ниже пишут, были серьёзные проблемы. Их было мало и учитывая, что "Сетунь" разрабатывали не для военных, а для академических целей, то транзисторов могли банально не дать. Тем более, что разработчики со старта планировали разрабатывать серийную машину.
Странно, Альварес пишет, что "Сетунь" отключили в 1986 и "наставник" адаптировали под ДВК-2. Добавил в статье. Возможно это была уже не "Сетунь"? Про "тяжело", полагаю да, ну так возраст... Ничего не поделаешь.
Истину глаголите. И это не только разработчиков это касается. Архитекторы, системные аналитики, тестировщики, дизайнеры - в точности аналогичная ситуация.
Юридически АМД≠ГлоФо. ГлоФо появилась, когда было принято отторгнуть основные фаундри компании. Более того в 2012 ГлоФо выкупила у AMD оставшиеся 8%. Но при этом AMD продолжает оставаться основным заказчиком и статус фаундера большинства заводов этой компании у неё никто не отберёт.
Смотря о каких исходных данных идёт речь. Спецификации и требования к системам, которые планируются к разработке, редко являются секретом, если же являются, то вытащить их из массива данных публичного ИИ, как нечто пригодное к "использованию" и сопоставить с конкретным пользователем - нетривиальная и отнюдь не простая задача.
Никаких обид, интересный вопрос. С радостью отвечу.
Начнём с примера который любезно сгенерил chat gpt.
Сомневаетесь, а зря (если я, конечно, дальше нигде не ошибся). В теории безусловно будет быстрее, в первую очередь за счет сокращения второй и третьей итерации и возможности обработать большую часть массива в первой и необходимом меньшем количестве операций по сравнению. Это происходит за счет уменьшения количества шагов, необходимых для нахождения элемента, так как на каждом шаге исключается больше неподходящих элементов:
В двоичном поиске, если у нас есть массив размером ( n ), то максимальное количество сравнений, которое потребуется сделать, составляет ( \log_2{n} ). В троичном поиске, это количество уменьшается до ( \log_3{n} ), что демонстрирует уменьшение количества шагов, так как ( \log_3{n} < \log_2{n} ) для любого ( n > 1 ).
Предположим существует упорядоченный массив из 27 элементов, если мы используем двоичный поиск потребуется до 5 сравнений, так как ( \log_2{27} ≈ 4.75 ), в троичном достаточно 3-х, так как ( \log_3{27} = 3 ).
Концепция троичных компьютеров (как и тетрарная система счисления) не популярна по целому ряду причин, которые я описал в статье. В первую очередь троичная логика не привычна и не типична, а создание тетраных компьютеров ограничено ресурсоёмкостью создания элементной базы и ПО для них - это время деньги, а прирост производительности может не окупить затрат. Я отнюдь не утверждаю, что всем совершенно необходимо перейти на троичные компы за десять лет и забыть про традиционные двоичные, но тема имеет право на существование.
Оспаривать то, что у потенциальных троичных систем есть очевидные математические преимущества, на мой взгляд абсурдно. В вычислениях больше теоретическое преимущество троичной системе даёт радиксная экономия ( R ) для системы счисления с основанием ( b ) и ( d ) цифрами - это отношение количества цифр ( d ) к логарифму по основанию ( b ) от ( d ):
[ R = \frac{d}{\log_b{d}} ]
Так у тетрарной системы, где b = 3, [ R = \frac{d}{\log_3{d}} ] , логарифмическая функция (\log_b{d} ) растет медленнее, чем линейная функция d. Радиксная экономия достигает минимума при b = e (основание натурального логарифма). ( e ) - не является целым числом и ближайшим к нему целым числом является 3.
Для двоичной системы( b = 2 ), [ R_{binary} = \frac{d}{\log_2{d}} ], значение ( R ) будет выше, чем для троичной системы. Соответственно в двоичной системе необходимо больше цифр для представления того же количества информации.
Очевидна более высокая информационная ёмкость, т.к. троичная система счисления даёт возможность хранить больше информации на единицу памяти (чисто математически), трит может представлять три состояния (-1, 0, +1), а бит представляет только два (0, 1).
Также симметричное представление чисел относительно нуля в уравновешенной тетрарной системе упрощает алгоритмы поиска и сравнения, так как числа можно сравнивать без необходимости отдельно учитывать отрицательные и положительные, например: В троичной системе, мы можем представить отрицательные числа, просто заменив их на отрицательный эквивалент. Например, если у нас есть троичное число a +1-10 (a==4), его отрицательная версия будет -1+10 (a==-4), итог - нет необходимости дополнительных шагов.
В двоичной системе несколько сложнее, инверсия числа включает инвертирование каждого бита (0 становится 1, и наоборот) и последующее добавление единицы к результату. Представим двоичное число a 0101 (a==5). Инвертирование каждого бита даёт нам 1010, добавляем 1 и получаем 1011(a==-5), появляется дополнительный шаг.
Это не всё, но это аргументационная база обоснований большей математической эффективности тетрарной системы счисления для использования в вычислительной технике. Полагаю, что именно по этим причинам Дональд Кнут считал, что "Возможно, самая красивая система счисления — это сбалансированная троичная"
Ага, из моей)
Ну как минимум сомножетили числа 15 при исполнении алгоритма Шора были найдены с использованием квантового компьютера. Факторизация числа 21, опять же. Эксперименты с квантовыми компьютерами проводятся всего 30 лет, очевидно этого не достаточно. Но тот же Google тратит миллионы на использование компьютеров D-Wave для получения выборок, на которые у классических компьютеров ушли бы сотни, если не тысячи лет. Тут вопрос стоимости эффективных решений и теоретической возможности создания универсального квантового компьютера. Тут я скорее квантовый оптимист, но понимаю, что эта история не будет быстрой.
Тут только вопрос о том каких транзисторов и каких устройств. Ну и цифра скромная, учитывая амбиции "догнать и перегнать". И, как я уже писал выше, речь про 1957-й год, когда "Сетунь" уже 2 года как разрабатывали и архитектура уже была создана.
Ну так это в 1957-м, а не в 1955-м (когда начали разрабатывать "Сетунь"), это во первых, а во вторых это через 3 года после начала серийного производства транзисторов, причем речь про все типы транзисторов. И не факт, что все они были годны к использованию, речь шла о том, сколько всего было выпущено, нет данных сколько из них отбраковали и в каких режимах, при каких нагрузках они могли работать. Все авторы того времени сходятся в едином мнении, что транзисторов был катастрофический дефицит и что советские транзисторы первого поколения были редкостным дерьмом, до середины 1960-х.
Это верно. И полагаю, что начали выпускать как раз для военки и космоса, но получив то, что получили, решили использовать хотя бы ширпотребе ибо качество было катастрофическим. Об этом пишут все, кто тогда жил, ну кроме журналистов официальной советской прессы (доверять журналистам и не доверять инженерам, я полагаю, абсурдно).
Думаю, что у авторов "Сетуни" просто небыло выбора.
Спасибо. Интересно, а дискуссия в итоге была, с разработчиками?
Спасибо. Многое становится яснее.) Исходный текст где можно найти? Ибо гуглить лень.
Единственным известным примером использования троичной машины в оборонке является "Сетунь" с тем же наставником. Об этом говорил Брусенцов, вскользь в интервью, о том, что кого-то где-то обучали при помощи наставника. Предположительно, часть из серийных "Сетуней" ушли куда-то по оборонной линии, но это не точно, делаю вывод из того, что не все были использованы в ВУЗах и на производствах. Предполагаю, что речь также шла об использовании в учебных заведениях. Особенности программирования на троичных машинах не позволяли использовать их массово, что часто необходимо в оборонке. Также есть основания полагать, что если бы на эти компы был военный заказ и осознанные перспективы применения в оборонке, то их судьба сложилась бы иначе.
См. выше о качестве, условиях производства и количестве выпускаемых транзисторов в СССР.
Для ширпотреб электроники они возможно были и годны, но и для военки, космоса и компьютеров - нет. Низкая термостабильность, большой разброс параметров. Главная проблема - советская культура производства. Вот вам цитата из «Основы радиолокационной техники. Часть II» (Военное издательство МО СССР, 1959) Е. А. Каткова и Г. С. Кромина:
И ещё одна Я. А. Федотова, Ю. В. Шмарцева из книги «Транзисторы» (Советское Радио, 1960):
К слову о количестве, в 1957 выпуск транзисторов в СССР составлял 2,7 млн шт, в США - 28 миллионов. Превысить порог в 10 млн в год, в СССР смогли только в 1966 году.
Нет.
Странно, что нет данных о том в каком количестве годную продукцию могли выпустить после. И сколько первых месяцев прошло.
О наличии транзисторов в СССР в этот период из уст Брусенцова: https://youtu.be/IO4-YwhyvrM?t=783
И тут же:
Я нигде не писал, что в 55-м начали серийное производство. И да, понимали из чего будут делать. Транзисторов мало, лампы - не подходят. Нужна альтернатива, ферритдиодная ячейка Гутенмахера - подходящая альтернатива. Схемотехника проще, надёжность выше, стоимость ниже, проблем с производством в товарных количествах - нет. И да, планировали создать компьютер, который подходил бы для серии. И таки создали. И в серию пошел, но она была небольшой, стартовала фактически в 1962 году.
Легенда же. Ну или намеренная деза), тоже как вариант. В Британии к 1956 Metrovick 950 уже сделали. Между тем сомнительность легенды не отменяет того факта, что с транзисторами, в том числе с плоскостными, о которых ниже пишут, были серьёзные проблемы. Их было мало и учитывая, что "Сетунь" разрабатывали не для военных, а для академических целей, то транзисторов могли банально не дать. Тем более, что разработчики со старта планировали разрабатывать серийную машину.
Терминал
Такой терминал был?
Странно, Альварес пишет, что "Сетунь" отключили в 1986 и "наставник" адаптировали под ДВК-2. Добавил в статье. Возможно это была уже не "Сетунь"?
Про "тяжело", полагаю да, ну так возраст... Ничего не поделаешь.
Истину глаголите. И это не только разработчиков это касается. Архитекторы, системные аналитики, тестировщики, дизайнеры - в точности аналогичная ситуация.
Юридически АМД≠ГлоФо. ГлоФо появилась, когда было принято отторгнуть основные фаундри компании. Более того в 2012 ГлоФо выкупила у AMD оставшиеся 8%. Но при этом AMD продолжает оставаться основным заказчиком и статус фаундера большинства заводов этой компании у неё никто не отберёт.
Спасибо, интересно. А о каком классе задач в обработке данных идёт речь?
Смотря о каких исходных данных идёт речь. Спецификации и требования к системам, которые планируются к разработке, редко являются секретом, если же являются, то вытащить их из массива данных публичного ИИ, как нечто пригодное к "использованию" и сопоставить с конкретным пользователем - нетривиальная и отнюдь не простая задача.