Представление чисел в памяти и точность вычислений

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

Микропроцессор рассчитан на определённую разрядность поступающих в него данных, у процессора определённое ограниченное количество ножек, каждая ножка отвечает за определённый двоичный разряд числа. Например, если процессор является 32-битным, то основной размер числа для него 32 бита, т.е. число размером 32 бита (4 байта) может быть передано в память или из памяти за один такт (один цикл обработки данных процессором).

Наиболее эффективным по скорости является использование "родной" для этого процессора разрядности: если процессор 16-битный, то это 16 бит, если 32-битный, то 32 бита. Если число больше по размеру (например: 40 бит для 32-битного процессора), то процессор будет его обрабатывать уже (минимум) в два прохода. Если число будет меньше чем 32 бита, то процессор всё равно не сможет обработать несколько чисел за такт, а если потребуется сложить или вычесть два числа с разной разрядностью, то потребуется ещё и привести их к разрядности большего числа. Так что самое выгодное с точки зрения скорости - использовать для всех целых чисел тип данных с "родной" для процессора разрядностью (например, при программированни на Delphi для 32-битных процессоров использовать тип Integer). С точки зрения экономии памяти выгодно использовать как можно меньше байт памяти (типы как можно меньшего размера).

Какие же числа можно представить в 8 битах? В одном бите можно представить только 2 значения: 0 или 1. В двух битах – 4 значения: 00, 01, 10, 11. В $N$ битах можно представить $2^N$ различных значений. Для целых неотрицательных чисел логично считать, что когда все разряды 0, то это число 0, а когда все разряды 1, то это максимальное число, которое в этом случае равно $2^N-1$.

Если число не укладывается ни в один из стандартных типов, то надо реализовывать "Длинную арифметику" (ссылка на урок по "Длинной арифметике").

Целые числа и дополнительный код

Дополнительный код - самый распространённый способ представления отрицательных целых чисел в компьютерах. Он позволяет заменить операцию вычитания на операцию сложения (используя свойства переполнения) и сделать операции сложения и вычитания одинаковыми для знаковых и беззнаковых чисел, чем упрощает архитектуру ЭВМ. Дополнительный код отрицательного числа можно получить инвертированием модуля двоичного числа (первое дополнение) и прибавлением к инверсии единицы (второе дополнение). Либо вычитанием числа из нуля.

Примеры:

1 => 00000001
0 => 00000000
-1 => 11111111

Инструмент исследования представления чисел в памяти

Для того чтобы исследовать формат представления переменных различных типов в памяти можно использовать следующий приём: создать указатель на массив байт и сделать, чтобы он ссылался на нужную нам исследуемую переменную и вывести побайтно содержимое памяти (столько байт, сколько занимает эта переменная).

{ Массив для вывода шестнадцатеричных цифр }
const Hex : array [0..15] of Char =
  ('0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F');

var
  X : Integer; { X - исследуемая переменная, Integer - исследуемый тип (замените на интересующий) }
  P : array of Byte = @X; { P - указатель на массив байт, который указывает на переменную X }
  i,j : Integer; { Переменные циклов }
begin
  { Считываем исходное значение }
  Readln(X);
  { Вывод в двоичной системе счисления }
  for i := sizeof(x) - 1 downto 0 do begin { Цикл по байтам (начиная со старшего) }
    for j := 7 downto 0 do { Цикл по битам (начиная со старшего) }
      write((P[i] shr j) and 1); { Получаем бит j: сдвигаем на j-бит вправо и берём последний бит }
    if i > 0 then write(' '); { Между байтами выводим пробел }
  end;
  writeln;
  { Вывод в шестнадцатеричной системе счисления }
  for i := sizeof(x) - 1 downto 0 do begin
    { Вывод 2-х шестнадцатеричных цифр - содержимое i-ого байта }
    write(Hex[P[i] div 16], Hex[P[i] mod 16]);
    if i > 0 then write(' ');
  end;
  writeln;
end.

Вместо массива шестнадцатеричных символов можно использовать функцию (в ней труднее ошибиться):

procedure out_hex_digit(b: Byte);
begin
  if b < 10 then write(chr(b + ord('0')))
            else write(chr(b + ord('A') - 10));
end;

В этом примере были использованы побитные операции:

A shr B - сдвиг числа A вправо на B бит (младшие биты при этом теряются).
A and B - побитная операция "И" в C := A and B бит будет установлен в 1, только если он 1 и в A и B.

Теперь, когда у нас есть программа для проведения экспериментов, мы можем изучить как представляются различные типы данных в памяти.

Неточность представления чисел с плавающей запятой

Как хранить нецелые числа в компьютере? Вариантов много. Можно, например, хранить их в виде рациональных дробей (тогда мы можем использовать механизм хранения целых чисел).

Любые типы данных в компьютере хранятся как последовательность бит. Для записи действительных чисел хранится порядок и мантисса. Т.е. число хранится как двоичная дробь. Вначале стоит точка, затем мантисса, а затем порядок (двоичная степень).

Любое действительное число не кратное 2 хранится неточно. С погрешностью в последнем бите мантиссы. Задача про сравнение это наглядно показывает.

uses SysUtils;
var a,b,c:extended;
begin
  reset(input,'eq.in');
  rewrite(output,'eq.out');
  readln(a,b,c);
  if (abs(a+b-c) < 0.0000001) then writeln('YES') else writeln('NO');
end.

Эксперимент на Delphi на точность сравнения

{$APPTYPE CONSOLE}

{ Сравнение без учёта погрешности машинного представления чисел }
function eq1(a,b,c:extended):boolean;
begin
  result := a+b = c;
end;

{ С учётом погрешности }
function eq2(a,b,c:extended):boolean;
begin
  result := abs(a+b-c) < 1e-17;
end;

var a,b,c : extended;
begin
  a := 0.1;
  b := 1.2;
  c := 1.3;
  writeln(a+b=c); // FALSE
  writeln(0.1+1.2=1.3); // TRUE, хотя написано, вроде бы, то же самое
  writeln(0.1+0.1+0.1-0.3=0.0); // TRUE
  writeln(1+0.1-1=0.1); // FALSE, как ни странно :)
end.

Для предоления проблем с точностью вычислений в языке программирования Python есть специальный тип Decimal, этот тип основан на модели чисел с плавающей точкой, которая разработана по принципу: "компьютер должен обеспечивать арифметические действия, которые работают так же, как людей обучают в школе".

Например: 0.1+0.1+0.1-0.3 в точности равно 0.

from decimal import *

Действительные числа (с плавающей точкой, floating point)

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

{$apptype console}
function convert(x : extended) : int64;
begin
  result := trunc(x);
  assert(abs(result) < int64(1) * 1000000 * 
                                  1000000 * 
                                  1000000);
end;
var a, b : extended;
begin
  a := -706378499182879656;
  b := -513623273852583522;
  writeln((a+b):0:0);
  writeln(convert(a) + convert(b));
end.