(n + 1) * (n + 1) = n*n + 2*n + 1 =>

  def g(n: Int): Int = if (n == 0) 0 else g(n - 1) + n + n - 1

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

"В качестве разминки напишите реализацию функции g(n), которая вычисляет n^2, используя из математических операций только + и –.Язык программирования любой, n — натуральное число, вспомогательные переменные использовать не рекомендуется".
На всякий случай, не заморачивайтесь с отрицательными числами.

Но как же без вспомогательных переменных?

Максимум, получилось следующее (но тут они неявно все равно будут в избытке) :
[spoiler]

int G(int n, int itreation = 1)
        {
            if (itreation == n)
                return n;
            return n + G(n, itreation + 1);
        }

[/spoiler]

Здравствуйте, vsb, Вы писали:

vsb>(n + 1) * (n + 1) = n*n + 2*n + 1 =>

vsb>

vsb>  def g(n: Int): Int = if (n == 0) 0 else g(n - 1) + n + n - 1
vsb>

ты бог! Но как ты до этого додумался?

Здравствуйте, Аноним, Вы писали:

А>как ты до этого додумался?

Предположил, что задачу можно попробовать решить с помощью рекурсии. Для этого надо выразить g(n + x) от предыдущих значений. Раскладываем (n+1)^2 и дальше всё очевидно.

Здравствуйте, vsb, Вы писали:
vsb>Предположил

Выглядело потрясающе, без шуток.
Если это не секрет, как такому можно научиться?
Мне кажется, это истинно математическое мышление.
Возможно ли в нем упражняться, или это преимущественно "от рождения"?

Здравствуйте, Аноним, Вы писали:

А>Пробегал глазами по рассылке вакансий, попалась интересная задачка:

А>"В качестве разминки напишите реализацию функции g(n), которая вычисляет n^2, используя из математических операций только + и –.Язык программирования любой, n — натуральное число, вспомогательные переменные использовать не рекомендуется".
А>На всякий случай, не заморачивайтесь с отрицательными числами.

А>Но как же без вспомогательных переменных?
К.м.к. вопрос на знание техники написания циклов в функциональных ЯП, когда в качестве вспомогательных переменных используешь параметры функции хвостового выхова http://ru.wikipedia.org/wiki/%D0%A5%D0%B2%D0%BE%D1%81%D1%82%D0%BE%D0%B2%D0%B0%D1%8F_%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F

Реккурентное решение явный оверкилл

Здравствуйте, Аноним, Вы писали:

А>"В качестве разминки напишите реализацию функции g(n), которая вычисляет n^2, используя из математических операций только + и –.Язык программирования любой, n — натуральное число, вспомогательные переменные использовать не рекомендуется".

Достаточно вообще инкремента-декремента... какое там определение функции Аккермана?

А>Но как же без вспомогательных переменных?

Да запросто. Но рекурсия — это нечестно, это те же вспомогательные переменные в неограниченном количестве.
Поэтому делаем так.

n^2 = 1 + 3 + ... + (2k-1) + ... + (2n-1)

int square(int n)
{
  int s = 0; // ну хоть одну переменную нам придётся завести
  // будем крутить цикл назад, от переменной правой границы к константной левой, чтоб правую не хранить и не вычислять
  for(n = n+n-1; n > 0; n = n-2)
    s = s + n;
  return s;
}

У всех оотэнное говно

int64_t mul (int64_t n, int64_t m, int64_t res, int64_t iter)
{
    return 
        (iter==m)        ? res :
        (iter+iter < m)  ?    mul(n, m, res+res, iter+iter) :
        res + mul(n, m-iter, n, 1); 
}

int64_t sqr(int64_t n)
{
    return mul(n, n, n, 1);
}

возведите миллион в квадрат вашим способом и моим

Здравствуйте, Кодт, то, что вы бог кода, я и раньше знал)

Но может быть Вы мне подскажите тогда.
Ведь главное метод и умение его применять в нужной ситуации, не так ли?

Не помню, чтобы в школе и институте учился чему-либо подобному.
Но на практике мне обычно помогало следующее:
1) Взять ручку и бумагу.
2) Записать результаты.
3) Выявить какую-то закономерность.

Простую закономерность мне увидеть не удалось, поэтому я забил.
Но у тех, кто отписался в этой теме метод несоизмеримо мощней — видимо следствие высокой математической культуры, с которой я не знаком, поэтому даже описать его не смогу.

Но главное в этом частном случае, как я понял из комментариев выше — это выразить F(N+1) через F(N)+<какие-то данные> (не уверен, что записано формально правильно).

Очевидно, это маленькая частность. Скажите, пожалуйста, как называется полный метод, можно ли его освоить, или это действительно целая культура? Тогда, все-таки, как она формируется.

Нечто похожее я встречал лишь однажды, но не уверен, что именно то — читал в читальном зале книгу Самарского по вычислительным методом, и там было что-то похожее про "рекурентные соотношения". По-моему, осуществлялся подобный вывод.

Здравствуйте, Аноним, Вы писали:


А>Очевидно, это маленькая частность. Скажите, пожалуйста, как называется полный метод, можно ли его освоить, или это действительно целая культура? Тогда, все-таки, как она формируется.

Рекуррентное соотношение.

Здравствуйте, Аноним, Вы писали:

А>Простую закономерность мне увидеть не удалось, поэтому я забил.
А>Но у тех, кто отписался в этой теме метод несоизмеримо мощней — видимо следствие высокой математической культуры, с которой я не знаком, поэтому даже описать его не смогу.

Эээ, закономерность. Столько всего с квадратами связано — и метод суммирования юного Гаусса, и производная параболы, и семейство алгоритмов Брезенхема.


А>Очевидно, это маленькая частность. Скажите, пожалуйста, как называется полный метод, можно ли его освоить, или это действительно целая культура? Тогда, все-таки, как она формируется.

А>Нечто похожее я встречал лишь однажды, но не уверен, что именно то — читал в читальном зале книгу Самарского по вычислительным методом, и там было что-то похожее про "рекурентные соотношения". По-моему, осуществлялся подобный вывод.

гуглить, например, "производящие функции"
Но в данном случае это из пушки по воробьям.

Спасибо!
Почувствовал мощь математики.

Здравствуйте, TarasB, Вы писали:

TB>У всех оотэнное говно
TB>возведите миллион в квадрат вашим способом и моим

У тебя слишком много переменных и не сделана концевая рекурсия.

Здравствуйте, Кодт, Вы писали:

К>У тебя слишком много переменных и не сделана концевая рекурсия.

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

Здравствуйте, TarasB, Вы писали:

TB>У тебя переменных больше. У меня ноль, у тебя одна.

То, что все твои переменные присваиваются единожды, ничего не значит. Их там не меньше 5 (для концевой рекурсии) или 4*log2(n) (для обычной).
А у меня, кстати, ровно две переменные.

Здравствуйте, Кодт, Вы писали:

К>То, что все твои переменные присваиваются единожды, ничего не значит. Их там не меньше 5 (для концевой рекурсии) или 4*log2(n) (для обычной).
К>А у меня, кстати, ровно две переменные.

А, так ты любую ячейку памяти считаешь переменной?
Ну тогда я могу свести свой к 4 переменным, если руками разверну цикл, определяющий двоичный логарифм множителя. Ну портянка из 63 ифов будет). А с появлением 128-битных процессоров её надо будет переписать.

Здравствуйте, TarasB, Вы писали:

TB>А, так ты любую ячейку памяти считаешь переменной?
TB>Ну тогда я могу свести свой к 4 переменным, если руками разверну цикл, определяющий двоичный логарифм множителя. Ну портянка из 63 ифов будет). А с появлением 128-битных процессоров её надо будет переписать.

Да. Указатель инструкции — это тоже переменная. А ты думал, будет легко?

Здравствуйте, Кодт, Вы писали:

К>Да. Указатель инструкции — это тоже переменная.

Указатель инструкции, регистр флагов, указатель на вершину стека... Тогда нифига у тебя не две переменные. Как именно ты их считаешь?

Кстати, твой код я могу увеличить на одну переменную, сделав портянку по степеням двойки ( n^2 = (n-2^m)^2 + 2*2^m*n — (2^m)^2 ). Одна лишняя переменная, зато алгоритмическое ускорение.
И ещё я понял, что достаточно разбирать лишь до 2^31, потому что дальше уже в квадрат не возводится, переполнение будет

Здравствуйте, TarasB, Вы писали:

TB>Указатель инструкции, регистр флагов, указатель на вершину стека... Тогда нифига у тебя не две переменные. Как именно ты их считаешь?

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

TB>Кстати, твой код я могу увеличить на одну переменную, сделав портянку по степеням двойки ( n^2 = (n-2^m)^2 + 2*2^m*n — (2^m)^2 ). Одна лишняя переменная, зато алгоритмическое ускорение.

Не понял, как считать по твоей формуле. Вот так получилось 5 переменных.

// n*n = n*2^k + n*(n-2^k)
int square(int n)
{
  int s = 0;
  int m = n; // правый множитель
  while(m > 0)
  {
    int p  = 1; // 2^k, k=0, 1, ...
    int pn = n; // p*n
    while(p+p <= m)
    {
      p  += p;
      pn += pn;
    }
    s += pn;
    m -= p;
  }
  return s;
}

TB>И ещё я понял, что достаточно разбирать лишь до 2^31, потому что дальше уже в квадрат не возводится, переполнение будет

Будем действовать, как gcc 4.8 -O2. "переполнения не бывает", а если оно происходит, то клиент ССЗБ.

Здравствуйте, Кодт, Вы писали:

К>Если размер кода или глубина стека разбухает кратно увеличению разрядности, то указатель инструкции или стека, соответственно, — это скрытая переменная.

Не понял. Эти указатели и так есть, при любой реализации.

К>Не понял, как считать по твоей формуле. Вот так получилось 5 переменных.
К>

К>// n*n = n*2^k + n*(n-2^k)
К>int square(int n)
К>{
К>  int s = 0;
К>  int m = n; // правый множитель
К>  while(m > 0)
К>  {
К>    int p  = 1; // 2^k, k=0, 1, ...
К>    int pn = n; // p*n
К>    while(p+p <= m)
К>    {
К>      p  += p;
К>      pn += pn;
К>    }
К>    s += pn;
К>    m -= p;
К>  }
К>  return s;
К>}
К>

Да, я это понял. Но если развернуть портянку ифов, перебрав все случаи двоичного порядка для m, то будет 4. А по схеме от n-2*k к n можно свести и до 3.

ПС еле нашёл тему, фиг тут поймёшь что куда переносится

TB>ПС еле нашёл тему, фиг тут поймёшь что куда переносится

Ага, я подумал, что рекрутеры пожаловались, и тему удалили

Здравствуйте, TarasB, Вы писали:

К>>Если размер кода или глубина стека разбухает кратно увеличению разрядности, то указатель инструкции или стека, соответственно, — это скрытая переменная.
TB>Не понял. Эти указатели и так есть, при любой реализации.

вот смотри

int square(int n) {
  int m = n; // множитель
  int s = 0; // сумматор

  assert(n < 32);

  if(m >= 16) {
    int t = n; t+=t; t+=t; t+=t;
    s += t;
    m -= 16;
  }
  if(m >= 8) {
    int t = n; t+=t; t+=t;
    s += t;
    m -= 8;
  }
  if(m >= 4) {
    int t = n; t+=t; t+=t;
    s += t;
    m -= 4;
  }
  if(m >= 2) {
    int t = n; t+=t;
    s += t;
    m -= 2;
  }
  if(m >= 1) {
    int t = n;
    s += t;
    m -= 1;
  }
}

С каждым новым битом у нас добавляется новый шаблонный кусок кода. То есть, мы сделали за компилятора такую работу

RUN <16> ();
RUN <8> ();
RUN <4> ();
RUN <2> ();
RUN <1> ();

и вот этот параметр — 1..16 — спрятали, синхронизировав с указателем инструкции.

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



TB>ПС еле нашёл тему, фиг тут поймёшь что куда переносится

http://rsdn.ru/Users/Private/MyRsdn.aspx?go=answers (в дереве: Мой RSDN — ответы мне)

Здравствуйте, Кодт, Вы писали:

К>С каждым новым битом у нас добавляется новый шаблонный кусок кода. То есть, мы сделали за компилятора такую работу
К>и вот этот параметр — 1..16 — спрятали, синхронизировав с указателем инструкции.

Ну спрятали, да. Ну и? Это параметр времени компиляции, а не выполнения.
Может ещё посчитать переменные, которые были у меня в голове, когда я придумывал этот код?

Я просто смысла уже не понимаю, сформулируй ясно, что именно мы считаем.

К>http://rsdn.ru/Users/Private/MyRsdn.aspx?go=answers (в дереве: Мой RSDN — ответы мне)

А, понял, а из гуя как выйти на эту ссылку?

Здравствуйте, TarasB, Вы писали:

TB>Ну спрятали, да. Ну и? Это параметр времени компиляции, а не выполнения.
TB>Может ещё посчитать переменные, которые были у меня в голове, когда я придумывал этот код?

TB>Я просто смысла уже не понимаю, сформулируй ясно, что именно мы считаем.

Смысл такой: если масштабирование задачи ведёт к перекомпиляции, — то значит, параметры времени компиляции тоже надо учитывать.
Иначе, в пределе, можно вообще одной переменной обойтись

unsigned int square(unsigned short n)
{
  if(i < 0x8000)
    if(i < 0x4000)
      if(i < 0x2000)
        ...
          if(i < 0x0002)
            if(i < 0x0001)
              return 0;
            else // [0x0001..0x0002)
              return 1;
          else
            if(i < 0x0003)
              return 4;
            else // [0x0003..0x0004)
              return 9;
        ...
    else // [0x4000..0x8000)
      if(i < 0x6000)
        ...
      else // [0x6000..0x8000)
        ...
  else // [0x8000..0xFFFF)
    ...
}

Тоже за логарифмическое время. По-твоему, это честно?

К>>http://rsdn.ru/Users/Private/MyRsdn.aspx?go=answers (в дереве: Мой RSDN — ответы мне)
TB>А, понял, а из гуя как выйти на эту ссылку?

Так я и говорю: www.rsdn.ru, дерево слева, в самом низу "Мой RSDN", ветка "ответы мне" или "мои сообщения"

Здравствуйте, Кодт, Вы писали:

К>Смысл такой: если масштабирование задачи ведёт к перекомпиляции, — то значит, параметры времени компиляции тоже надо учитывать.

Заточка кода под новую разрядность всегда ведёт к перекомпиляции.

К>Иначе, в пределе, можно вообще одной переменной обойтись
К>Тоже за логарифмическое время. По-твоему, это честно?

Да, можно. Насчёт честности — условия надо уточнять. Что мы минимизируем? Число занятых регистров? Объём исполняемого кода? Скорость исполнения? Или всё вместе с какими-то весами? А скорость на чём мерять, что это за экзотический процессор, не умеющий умножать?

К>Так я и говорю: www.rsdn.ru, дерево слева, в самом низу "Мой RSDN", ветка "ответы мне" или "мои сообщения"

Спасибо.