Немного хаоса в этот блог 3 (как перевести дробное число в двоичную систему счисления)
Возвращаясь к теме деления в разных системах счисления.
Так исторически сложилось, что люди пользуются десятичной системой счисления. Почему люди используют эту глупость? Люди раньше считали на пальцах. Пальцев у нас десять. Загибая пальцы на руках, можно легко и непринужденно посчитать количество баранов в стаде. Правда, если в стаде больше 10 баранов - начинаются проблемы. Приходится загибать пальцы и на ногах. Самое смешное, что используя всего десять пальцев на руках, можно так же легко и непринужденно посчитать до тысячи (до 1023, если быть точнее). А если и на ногах пальцы загибать - можно до миллиона досчитать (2^20-1=1048575).
Как мы считаем в десятичной системе счисления?
Считаем: 0, 1, 2, ..., 9. Закончились знаки. Записали единичку в следующий разряд. Продолжаем: 10, 11, 12, ..., 19. Еще одну единичку добавили в следующий разряд. 20, 21, ..., 97, 98, 99. Добавляем еще один разряд. 100, 101, 102 и т.д.
В двоичной системе считаем так же, только знаков у нас меньше. Вместо знаков от 0 до 9 используем знаки от 0 до 1.
Считаем: 0, 1. Закончились знаки. Записали единичку в следующий разряд. Продолжаем: 10, 11. Добавили еще один разряд: 100, 101, 110, 111, 1000, 1001 и т.д.
Переводить числа из десятичной системы счисления в двоичную, настолько легко, что данную операцию можно проделать в уме. Чтобы перевести из десятичной системы в двоичную, надо разложить число на степени двойки.
Степени двойки:
2^0=1
2^1=2
2^2=4
2^3=8
2^4=16
2^5=32
2^6=64
2^7=128
2^8=256
2^9=512
Если трудно в уме считать, можно под каждую степень выделить отдельный палец. 2 в 0-й степени - 1-й палец, 2 в 9-й степени - 10-й палец. Раскладывая число, загибать (или оставлять не загнутым) соответствующий палец.
Например, нам надо перевести число 233 из десятичной системы в двоичную. Раскладываем:
233-128=105 (загибаем 8-й палец)
105-64=41 (7-й палец)
41-32=9 (6-й палец)
16 не отнимаем (5-й палец оставляем не загнутым)
9-8=1 (загибаем 4-й палец)
4 и 2 пропускаем (3 и 2 палец соответственно)
остается 1 (загибаем 1-й палец)
И смотрим, что мы там назагибали: 11101001 - так выглядит число 233 в двоичной системе счисления.
Вот так легко и непринужденно на пальцах посчитали до 233.
Переводить обратно, из двоичной системы в десятичную, так же легко.
Например, есть у нас число 1001100010. Страшное число? Ничего страшного. Там, где нолики - степень двойки пропускаем. Оставшиеся суммируем. Единичка слева - 512, два нуля пропустили, дальше 64 и 32, три нуля пропустили, дальше 2 и следующий ноль пропустили. Суммируем: 512+64+32+2=610. Опять же в уме можно посчитать.
Это все хорошо, но как быть с дробными числами. Или, скажем, с иррациональными числами? Расскажу о двух интересных способах, которые придумал на прошлой неделе.
Первый способ чисто геометрический.
Для начала, небольшое лирическое отступление. Делением двух взаимно простых чисел (меньшего на большее) можно получить уникальную десятичную дробь больше 0 и меньше 1. Уникальность ее заключается в том, что данную дробь нельзя получить делением пары других взаимно простых чисел. Например, взяли два взаимно простых числа - 7 и 11. Поделили меньшее на большее. Получили дробь 0.63(63). Дробь уникальная - другой парой взаимно простых чисел ее не получить.
Так вот, геометрический способ.
Есть у нас дробь 0.63(63). Взяли отрезок (0, 1). Отметили на отрезке нашу дробь (точка 0.636363...) Разделили отрезок на две равные части (точкой 0.5). Далее смотрим, в какой части отрезка находится наша точка. Если в левой - записываем 0, в правой - 1. Наша точка находится в правой части отрезка, поэтому записываем 1 (после запятой, то есть 0.1). Далее проделываем ту же операцию с отрезком, в котором находится наша точка - с отрезком (0.5, 1). Делим на две равные части точкой 0.75. Искомая точка (0.636363...) находится в левой части. Записали 0 (0.10). И так далее. Чисто визуально:
Каждый следующий отрезок масштабировал до размеров исходного, для пущей наглядности. В правой части точка - 1, в левой - 0. Сверху вниз: 101000101110. Собсно это и есть дробная часть 7/11 в двоичной системе счисления.
Очевидно и примечательно то, что данный паттерн зациклен для рациональных чисел (красной стрелочкой отметил отрезок, который после масштабирования повторяет исходный). В каком смысле "зациклен"? В том смысле, что после нескольких итераций, наш полученный отрезок в точности копирует один из предыдущих отрезков (с учетом масштабирования, естессно). Не обязательно исходный, что немаловажно. Например, два дробных числа 3/10=0.3 и 4/5=0.8:
Скрипт выложил сюда: http://xcont.com/binarysearch/ Можете вбить свои дробные числа (от 0 до 1) и получить такие же замечательные картинки.
Также примечательно то, что паттерн никогда не зациклится для иррациональных чисел. Для иррационального числа, точка будет хаотично находиться то в левой части отрезка, то в правой, ни разу не повторяя свою траекторию. Это поражает воображение!
В качестве примера, дробная часть всеми любимого числа Pi:
Дробная часть числа Эйлера:
Делить в двоичной системе проще и нагляднее, чем в десятичной. Можно разделить два числа с помощью листочка в клеточку и ножниц. Возьмем, для примера, опять же наше число 7/11. Отрезали от листочка ленту на 11 клеточек. Отметили 7 клеточек на ленте, поставили точку:
Согнули пополам. Если точка слева от места изгиба - 0. Справа - 1. На месте изгиба разрезали. Взяли ту часть ленты, в которой находится наша точка. Согнули, разрезали и т.д. Элементарно! И не надо никаких делений в столбик.
Отлично. Есть у нас простой, интуитивно-понятный и геометрически-наглядный способ деления чисел. Поделим все, что можно и нарисуем парочку графиков.
На графике:
16 картинок. На каждой картинке начало координат - левый верхний угол. Берем координату X, делим на координату Y. Получаем двоичное число. Берем дробную часть числа. На первой картинке закрашиваем соответствующий пиксель белым, если первый знак после запятой = 0 (если = 1 - черный пиксель). На второй картинке берем второй знак после запятой. И т.д.
Взял только 16-й знак после запятой от деления Y на X, нарисовал картинку 1000х1000:
Паттерны похожи на паттерны, которые можно нарисовать с помощью тригонометрической функции z=sin(a*x/y). Они не просто похожи, а в точности соответствуют. Для a=pi*(2^n), sin(a*x/y) будет меньше 0, если в (двоичной) дроби x/y соответствующий знак n после запятой = 1. Получили тригонометрический способ перевода десятичной дроби в двоичную. Считаем sin(pi*(2^n)*x/y) для n = 0, 1, 2, ... Если значение фукнции больше 0 - записываем 0. Если меньше - 1.
В качестве примера возьмем нашу дробь 7/11.
sin(pi*(2^n)*(7/11)) для n от 0 до 15:
0.9096319953545184
-0.7557495743542582
0.9898214418809328
-0.28173255684142895
0.5406408174555962
0.9096319953545171
0.7557495743542624
-0.9898214418809309
0.2817325568414538
-0.5406408174556399
-0.9096319953545601
-0.7557495743541267
0.98982144188099
-0.28173255684065845
0.5406408174542452
0.9096319953531827
Меняем положительные числа на 0, отрицательные - на 1. Получаем 0101000101110100.
Данный способ работает для любой периодической дроби. Периодической в двоичной системе. Непериодическими (конечными) дробями в двоичной системе являются только несократимые дроби, у которых в знаменателе находится степень двойки.
Данный способ работает и с иррациональными числами:
Число e-2=0.71828182845, в двоичной:
0.1011011111100001
sin(pi*(2^n)*(e-2)):
0.77394268526
-0.98020715847
0.38811216212
-0.71537776606
-0.99972311483
0.04704836214
-0.09399252276
-0.18715281753
-0.36769195818
-0.68386854177
-0.99790815372
-0.12902480447
0.25589266685
0.4947455432
0.85990524205
0.87788361623
-0.84079136654
Число Pi в двоичной:
11.00100100001111110
sin((pi^2)*(2^n))
-0.430301217
0.77685321961
0.97834055126
-0.4050366074
0.7406503198
0.99527211376
-0.19333318552
0.37937119883
0.70202227493
0.99989732814
0.02865595953
-0.057288383
-0.11438859336
-0.22727551212
-0.44265565094
-0.79385128143
-0.96550090052
0.50283231686
На закуску еще один график
Белый пиксель - если цифры после запятой закончились. На первой картинке - закончились сразу после запятой. На второй картинке - закончились на второй позиции и т.д. В двоичной системе.