Как ускорить функцию?

Question

[hagirangi]

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

type mass=array[0..300] of string;
var k,n,i,j:integer;
    m:mass;
function slog(s,s1:string):string;
type mass=array[1..1000] of integer;
var i,m,k,p:integer;
    a,b,c:mass;
    sres,sk:string;
begin
     if length(s)>length(s1)
     then m:=length(s)
     else m:=length(s1);
     k:=0;
     for i:=length(s1)+1 to m do
         s1:='0'+s1;
      for i:=length(s)+1 to m do
         s:='0'+s;
     for i:=1 to M do
         a[m-i+1]:=ord(s[i])-48;
     for i:=1 to m do
         b[m-i+1 ]:=ord(s1[i])-48;
     for i:=1 to  m do  begin
         p:=a[i]+b[i]+k;
         c[i]:=p mod 10;
         k:=p div 10;
         if (i=m) and (k<>0)
         then inc(m);
         c[i+1]:=k;
     end;
     sres:='';
     for i:=m downto 1 do
     begin
          str(c[i],sk);
         sres:=sres+sk;
     end;
     slog:=sres;
end;

Как я понял от тех кто уже ответил надо увеличить кол-во чисел в одной ячейке массива а как это сделать считывая строку я незнаю (помогите очень прошу)

Comments

[Антон Федорян]

уменьшить скорость её работы

может все-таки увеличить, а уменьшить время работы?

Как изначально звучит задание?

Answer 1

[Антон Федорян]

program addition;

// обычное сложение в столбик
function add(a, b: string): string;
const
  OFFSET = 48;
var
  tmp: integer;
  carry: integer;
  index_a,
  index_b: integer;
  addend_a,
  addend_b: integer;
begin
  result := '';
  
  // индексы последних цифр в каждой строке, т.к. сложение начинается справа налево
  index_a := length(a);
  index_b := length(b);
  
  // значение переноса, то что держим в уме, когда в сумме получаем двузначное число
  // например, 9 + 4 = 13: 3 пишем, а 1 в уме
  carry := 0;
  // продолжаем складывать, пока не пройдем по всем числам каждой строки
  while (index_a <> 0) or (index_b <> 0) do
  begin
    // первое и второе слагаемые
    addend_a := 0;
    addend_b := 0;
    
    // вместо выравнивания строк (дополнения нулями слева), я проверяю чтобы индекс не уходил в минус
    if index_a > 0 then
    begin  
      addend_a := ord(a[index_a]) - OFFSET;
      dec(index_a);
    end;
    
    if index_b > 0 then
    begin  
      addend_b := ord(b[index_b]) - OFFSET;
      dec(index_b);
    end;
    
    // собственно само сложение
    tmp := addend_a + addend_b + carry;
    carry := tmp div 10;
    result := chr((tmp mod 10) + OFFSET) + result;
  end;
  
  if carry > 0 then
    result := chr(carry + OFFSET) + result;
end;

begin
  writeln(add('999999999999999', '8009730000456465480001'));
  // 8009731000456465480000;
end.

Comments

[hagirangi]

можешь примерно написать как сделал чтобы так быстро работало не (с копированием строк, а не изменение)?У тебя работает в 2 раза быстрее чем у меня.Ну или хотя бы как работает программа.

[Антон Федорян]

hagirangi, написал небольшие комментарии к коду

[hagirangi]

Спасибо, это намного эффективнее чем держать все в массиве.

Answer 2

[Mercury13]

Название, конечно, не по прогерскому фэншую, и вспоминается знаменитый стих столетней давности:
«We slog, slog, slog, slogging over Africa,
Boots, boots, boots, boots moving up and down again».

ПЕРВОЕ. Главный тормоз — дополнение строк нулями, которое квадратичное по скорости.

for i:=length(s1)+1 to m do
         s1:='0'+s1;
      for i:=length(s)+1 to m do
         s:='0'+s;

Как решить?

function add1(const large,small:string):string;

function add(const x, y : string) : string;
begin
  if length(x) > length(y)
    then add := add1(x, y)
    else add := add1(y, x);
end;

Ну и разумеется, сделать, чтобы add1 работала с числами разной длины.

ВТОРОЕ. У вас, по-видимому, ошибка — 99+1 = 100 не создаст третьего разряда.

ТРЕТЬЕ. Я не знаю, какой у вас Паскаль, но, вероятно, передача строк по const/var также повысила бы скорость.

ОФТОП. Если ваша задача не «ввести два числа, сложить и всё», я бы отделил длинное число от его строкового представления, примерно так.

TLongNum = record
  length : integer;
  data : array [1..1000] of byte;
end;

Comments

[hagirangi]

Про сложить 2 числа это подзадача ( общая задача на Дин. программирование) Найти кол-во вариантов, про дополнение строк там как бы выше находится максимальная длина+1 специально чтобы если это наибольшая строка цикл ниразу не выполнялся (m),сложение работает нормально так как на тесте получаю только timelimit. Насчёт var передачи вполне вероятно.

Answer 3

[tester12]

Воспользуйтесь готовыми библиотеками. Например, этой - benibela/bigdecimalmath.

Если всё-таки хочется самодельного велосипеда, уберите все эти string и ord. Зачем хранить разряды в символах строки, чем не угодил массив чисел? Зачем делать разряды десятичными, почему их не сделать, например, 16-битными?

Comments

[hagirangi]

Насчёт 16-бит незнаю( если можешь напиши (код)), я так то и храню в массиве '0' нужны для приравнивания строк и вопрос как ты без ord строку в число переведёшь, в задаче надо использовать строку так как числа очень большие по итогу получаются.