Отправляет email-рассылки с помощью сервиса Sendsay

Система компьютерной алгебры GAP

Подписаться Бесплатная «Серебряная» новостная рассылка . Временно не выходит ,возобновит выход - нет информации Подписчиков 783 RSS
←   Февраль 2007   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


За последние 60 дней ни разу не выходила


Сайт рассылки: http://www.gap-system.org/ukrgap/
Открыта: 05-02-2002

Автор
Александр Борисович Коновалов

Статистика

783 подписчиков
0 за неделю
←   Все выпуски   →

Система компьютерной алгебры GAP - системы счисления в GAP


Добрый день!

На сайт Украинской группы пользователей GAP в раздел "Изучаем алгебру с GAP" добавлен следующий материал:

Реализация систематических чисел в GAP

(по материалам курсовой работы П. Москалева, декабрь 2005 г.)

Данная работа на примере достаточно простых объектов (таких, как систематические числа), описывает методику корректного расширения функциональности системы компьютерной алгебры GAP. Мы не ставим себе цель реализовать весь спектр действий над систематическими числами, а лишь показываем, как правильно создавать в GAP новые объекты и вводить операции над ними.

Следует отметить, что пользователь, работая с GAP, проходит четыре основных этапа:

  1. интерактивный режим;
  2. написание собственных программ;
  3. создание новых методов для уже существующих объектов;
  4. создание новых объектов и методов для работы с ними.
Мы показываем, как нужно действовать, находясь на четвертом этапе работы с системой.

Напомним, что системой счисления называется набор символов, с помощью которых записываются числа (их называют цифрами), и правил для выполнения действий над числами.

Систематическим числом называется число, записанное в некоторой системе счисления. Для того, чтобы перевести число из системы счисления с основанием p в систему с основанием q, необходимо делить это число, а затем и неполные частные в системе p на q. Остатки от деления и будут цифрами.

Теперь начнем разработку библиотеки.

Все наши функции будут размещены в двух файлах SysNum.gd, SysNum.gi. Первый будет содержать так называемую «декларативную» часть программы (т.е. в нем будут объявлены тип объекта, его внутреннее представление и функции для создания объектов). Второй – «исполняемую», в которую будет помещена реализация объявленных ранее функций и методов.

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

Каждый объект системы имеет свой тип. Согласно документации, тип объекта включает несколько аспектов информации об объекте. Семейство определяет, как объект взаимодействует с другими объектами, категория определяет перечень допустимых операций над объектом, представление определяет, в каком виде, фактически, будет представлен объект, и, наконец, атрибуты содержат другую информацию об объекте. В итоге можно сформулировать понятие типа, как степень отличия нашего объекта от других объектов системы.

Для начала нам нужно определиться с семейством систематических чисел. Наиболее простой способ – поместить все р-ичные числа в своем собственном кольце Integers base <p>. Тогда, например, 2-ичные и 3-ичные числа будут лежать в разных семействах, и действия над двумя числами будут возможны только в том случае, если они принадлежат одному семейству.

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

DeclareCategory( "IsSystematicNumberObj", IsScalar );
DeclareCategoryCollections( "IsSystematicNumberObj" );

Таким образом, все элементы колец Integers base <p> лежат в категории IsSystematicNumberObj, которая является подкатегорией IsScalar. Данная принадлежность означает, что над числами можно выполнять стандартные арифметические операции – сложение, вычитание, умножение, деление, возведение в степень и др.

Далее объявляется внутреннее представление чисел:

DeclareRepresentation( "IsSystematicNumberRep", IsPositionalObjectRep, [ 1 ] );

Наиболее простой способ хранения чисел – это хранить список цифр, и ничего более. Именно такое внутреннее представление мы и выбрали (IsPositionalObjectRep – список, причем список цифр числа – это первый элемент этого списка). Если бы наш объект имел более сложную структуру (например, это была бы группа со множеством атрибутов), то удобнее было бы использовать запись – IsComponentObjectRep.

DeclareGlobalFunction( "SystematicNumberObj" );
DeclareGlobalFunction( "SystematicNumbersRing" );
DeclareOperation( "Digits", [ IsPosInt, IsPosInt ] );
DeclareGlobalFunction( "SystematicNumber" );
DeclareGlobalFunction( "TransformNumber" );

Их назначение описывается ниже.

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

SystematicNumberObj – системная функция, создающая объект (число) по его семейству Fam и списку цифр digits:

InstallGlobalFunction( SystematicNumberObj, function( Fam, digits ) 
return Objectify( NewType( Fam, IsSystematicNumberObj and
  IsSystematicNumberRep ), [ digits ] );
end );

SystematicNumbersRing – вызывается пользователем, создает кольцо b-ичных чисел, в случае, если b целое положительное.

InstallGlobalFunction( SystematicNumbersRing, function( b )
local F, R;
  if not IsPosInt( b ) then
  Error( " must be a positive integer" );
fi;
F := NewFamily( Concatenation( String( b ), "-base numbers"),
                IsSystematicNumberObj );
F!.base := b;
R := RingWithOneByGenerators( [ SystematicNumberObj( F, [ 1 ] ) ] );
SetIsWholeFamily( R, true );
SetName( R, Concatenation( "Integers base ", String(
b ) ) );
return R;
end );

Знак "!." дает доступ к так называемым полям объекта. Команда SetIsWholeFamily говорит, что в R содержатся все b-ичные числа для заданного b.

Метод Digits переводит целое положительное десятичное n в систему счисления по основанию b (естественно, что b – целое положительное). 

InstallMethod( Digits,
[ IsPosInt, IsPosInt ],
  function( n, b )
  local digits, d, i;
    digits := [ ];
    i := 1;
    d := n;
    while true do
    if d < b then
      digits[ i ] := d;
      break;
    fi;
    digits[ i ] := d mod b;
    d := ( d - digits[ i ] ) / b;
    i := i + 1;
  od;
  return Reversed( digits );

 end );

Пользователь может использовать этот метод для получения систематического числа в виде списка.

SystematicNumber – пользовательская функция, используемая для создания систематического числа n в кольце R. Ясно, что перед ее вызовом пользователь должен создать кольцо R с помощью функции SystematicNumbersRing.

 
InstallGlobalFunction( SystematicNumber, function( R, n )
  local digits, b, F;
  b := FamilyObj( GeneratorsOfRingWithOne( R )[ 1 ] )!.base;
  digits := Digits( n, b );
  F := FamilyObj( GeneratorsOfRingWithOne( R )[ 1 ] );
  return SystematicNumberObj( F, digits );
  end );

Метод PrintObj – это стандартный метод системы для отображения созданного объекта. В данном случае он последовательно выводит цифры числа, причем если цифра больше 9, она берется в скобки ().

InstallMethod( PrintObj, 
               [ IsSystematicNumberObj and IsSystematicNumberRep ],
  function( x ) 
  local i, d;
  d := x![ 1 ];
  for i in d do
    if i > 9 then
      Print( "(", i, ")" );
    else 
      Print( i ); 
    fi;
  od;
  end );

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

InstallGlobalFunction( TransformNumber,
  function( x )
  local d, b, i, n, L;
  d := x![ 1 ]; 
  b := FamilyObj( x )!.base;
  n := 0;
  L := Length( d );
  for i in [ 1..L ] do
    n := n + d[ i ] * ( b^( L - i ) );
  od;
  return n;
  end );
Далее инсталлируются методы для арифметических операций. Заметьте, что целью данной работы являлась демонстрация на простом примере способа конструирования новых объектов и введения новых операций, эффективность выполнения этих операций в данном случае не учитывалась. Поэтому числа из системы счисления с основанием FamilyObj( x )!.base сначала переводятся в десятичную систему, затем над ними выполняются действия, после чего результат опять переводится в систему счисления с нужным основанием. Разработку методов, не использующих переход к десятичной системе счисления, мы оставляем читателю в качестве упражнения. 

InstallMethod( \=, 
               IsIdenticalObj, 
               [ IsSystematicNumberObj and IsSystematicNumberRep, 
               IsSystematicNumberObj and IsSystematicNumberRep ], 
  function( x, y ) 
  return x![ 1 ] = y![ 1 ]; 
  end ); 

InstallMethod( \+,
               IsIdenticalObj, 
               [ IsSystematicNumberObj and IsSystematicNumberRep,
                 IsSystematicNumberObj and IsSystematicNumberRep ], 
  function( x, y ) 
  return SystematicNumberObj(FamilyObj(x), 
                             Digits( TransformNumber(x)+TransformNumber(y), 
                                     FamilyObj( x )!.base ) ); 
  end );


InstallMethod( \*,
               IsIdenticalObj, 
               [ IsSystematicNumberObj and IsSystematicNumberRep,
                 IsSystematicNumberObj and IsSystematicNumberRep ], 
  function( x, y ) 
  return SystematicNumberObj(FamilyObj(x), 
                             Digits( TransformNumber(x)*TransformNumber(y),
                                     FamilyObj(x)!.base ) ); 
  end );

InstallMethod( \<, 
               IsIdenticalObj, 
               [ IsSystematicNumberObj and IsSystematicNumberRep,
                 IsSystematicNumberObj and IsSystematicNumberRep ], 
  function( x, y ) 
  return TransformNumber( x ) < TransformNumber( y ); 
  end );

InstallMethod( \^, 
               IsIdenticalObj, 
               [ IsSystematicNumberObj and IsSystematicNumberRep,
                 IsSystematicNumberObj and IsSystematicNumberRep ], 
  function( x, y ) 
  return SystematicNumberObj( FamilyObj( x ), 
                              Digits( TransformNumber(x)^TransformNumber(y), 
                                      FamilyObj( x )!.base ) ); 

 end );
Функция IsIdenticalObj делает возможным использование всех этих методов лишь для объектов из одного семейства.

Знак «\» перед названием метода используется при инсталляции бинарных операций, если символ операции ставится между операндами.

Теперь приведем различные примеры работы с библиотекой:

gap> Read("SysNum.gd");
gap> Read("SysNum.gi"); 
gap> R := SystematicNumbersRing( 2 ); 
Integers base 2 
gap> a := SystematicNumber( R, 2 ); 
10 
gap> b := SystematicNumber( R, 3 ); 
11 
gap> a+b; a*b; a^b; a=b; a<b;
101
110
1000
false
true
gap> D := SystematicNumbersRing( 10 ); 
Integers base 10 
gap> d1 := SystematicNumber( D, 2 ); 
2 
gap> d2 := SystematicNumber(
D, 3 ); 
3 
gap> d1+d2; 
5 
gap> d1*d2; 
6 
gap> (d2^d1)^d2*d1; 
1458 
gap> (3^2)^3*2; 
1458 
gap> H := SystematicNumbersRing( 16 ); 
Integers base 16 
gap> h1 := SystematicNumber( H, 10 ); 
(10) 
gap> h2 := SystematicNumber( H, 13 ); 
(13) 
gap> h1+h2; 
17 
gap> SystematicNumber( H, 23 );      
17
gap> h3 := SystematicNumber( H, 16 ); 
10 
gap> h3^2; 
100 
gap>
h3+h3; 
20

Таким образом мы видим, что наша библиотека корректно работает с различными системами счисления.

Для работы с библиотекой нужно загрузить файлы sysnum.gd и sysnum.gi, и прочитать их с помощью команды Read в том же порядке.

С уважением,

ведущий рассылки Коновалов А.Б.
В избранное