LINUX.ORG.RU

Продолжаем тему распределённого lc-генератора.

 , , ,


1

3

Кому лень читать - надо сделать(подсказать куда копать) x*3877 mod 139968, где x = 0(а может и от одного)...139967 на 32битных числах(а в идеале на float), быстро. Быстро - это максимум штук десять умножений/сложений.

Всем кто помог в прошлой теме - спасибо. В конечном итоге вышло это: http://pastebin.com/rnLwXiUv

//g++ main.cpp -Ofast -march=native -flax-vector-conversions -std=gnu++1y -pthread//пока только avx intel sb+
(0.914s)13.53tpc
(0.073s)1.08tpc

Это конечно хорошо(на самом деле оно тупо упирается в память и реально - оно раз в 20быстрее).

Но этого мало, проблема в том, что оно на даблах из-за «быстрого» «деления» и из-за того, что интел забил на целочисленную арифметику. Ну из-за пту.

Т.е. даблы только из-за:

double mod_139968(double n) {
  return n + (floor(n * 1. / 139968) * -139968);
}
//n * 1. / 139968 - конкретно этого

Я пытался смочь сделать это на 32битных интах - у меня не вышло, ибо пту. Прошу помощи.

dikiy GPFault

А ещё можно воспользоваться хорошей кармой данных чисел: (3877 * 2^8) mod 139968 = 12736 получается довольно маленьким, что позволяет сложить в один float первые_8_бит*3877 + остальные_биты*12736

По количеству операций это выглядит более перспективно - битовые операции более простые «разделение на байты» и 4 умножения, 2 сложения

#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <assert.h>

float mod_by_139968(float x)
{
	const float float_divider = 1./139968.;
	return x - 139968.f * floorf(((float)x) * float_divider);
}

const float low_mul = 3877;
const float high_mul = (3877 * 1<<8) % 139968;

float floats_nodivision_for_special_numbers(float x)
{
	float low_byte = ((int)x) & 0xff;
	float high_part = (((int)x) >> 8);
	return mod_by_139968(low_mul * low_byte + high_mul * high_part);
}

int basic(int x)
{
	return  (x*3877)%139968;
}

int main()
{
	assert(low_mul * 0xff + high_mul * (139967 >> 8) < 1 << 23);
	int x = 0;
	for(;x < 139968;++x)
	{
		if (basic(x) != floats_nodivision_for_special_numbers(x))
		{
			break;
		}

	}
	printf("sizeof(float) = %d; exiting with x = %d", sizeof(float), x);
	return 0;
}

это работает и с -Ofast.

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

GPFault ★★
()
Ответ на: комментарий от GPFault

Спасибо, отличная идея. Отпугивало она меня свой сложностью + проблемы после модуля, но второе решение особенно хорошо.

битовые операции более простые

Сдвиг дорогой.

Грубо. сложение + 2 умножения + битоп + сдвиг. Это такт с 2-х fma + такт со сдвига. В районе 2.5 тактов, если учитывать фантомный 3-й модуль * 2 модуля полных и того 5тактов. Т.е. это выгодно. Там дальше можно выкинуть одну конвертацию.

Но с флоатом ещё одна проблема:

(3877 ^ n * 42 + ((3877 ^ n - 1) / (3877 - 1)) * 29573) (mod m)
//139968*4*29573 уже не сможет

Переходить на int то же не вариант, ибо он медленнее.

registrant27492
() автор топика
Ответ на: комментарий от GPFault

Кстати, если речь идёт о работе на x86

Да.

возможно стоит просто использовать массив предвычисленных значений - уместится в кеш процессора.

Табличкой? 139968 флотов? Будет раз в 20медленней текущей реализации.

registrant27492
() автор топика
Ответ на: комментарий от registrant27492

К сожалению я не очень в курсе актуальных сложностей операций на x86-платформе - на моих дешёвых ARMах наоборот всё на int перевожу)

По идее непосредственно сдвиг для float не нужен - он может быть заменён AND, зануляющим младшие 8 бит. Потом множитель high_mul можно взять в 256 раз меньше (без потери точности множителя, так как он во float).

Или And тоже дорогой?

GPFault ★★
()
Ответ на: комментарий от GPFault

К сожалению я не очень в курсе актуальных сложностей операций на x86-платформе - на моих дешёвых ARMах наоборот всё на int перевожу)

Ну сейчас на х86 трупут fma в 2раза выше, чем у целочисленного умножения/сдвига и такое же, как у целочисленного сложения.

Т.е. да, сейчас на х86 сделать 2сложения+2умножения стоит столько же, сколько сделать сдвиг/умножить.

Это исправили(частично) только в самом последнем штеуде.

По идее непосредственно сдвиг для float не нужен - он может быть заменён AND, зануляющим младшие 8 бит. Потом множитель high_mul можно взять в 256 раз меньше (без потери точности множителя, так как он во float).

Спасибо.

Или And тоже дорогой?

Да, флотовский and стоит столько же, сколько и сдвиг, но это быстрее, ибо сдвига для флоатов там нет и приходится кастовать, на это там есть пенальти.

И флоатовый and то же исправили.

registrant27492
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.