Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Степень по модулю  [new]
q111
Guest
Необходимо селектом вычислить степень числа по модулю (a^t)%m. Числа могут быть большие, поэтому использование power невозможно

Пока есть рекурсивный вариант для MS SQL 2005
with t1(a,t,m) as(select 2,5,29 union all select 6,4,23)

,t2 as(select m,t,a,k=t,c=a,b=1 from t1
union all
select m,t,a,
case when k%2=0 then k/2 else k-1 END,
case when k%2=0 then (c*c)%m else c end,
case when k%2=0 then b else (b*c)%m end
from t2 where k>0)

select a,t,m,b from t2 where k=0

option (maxrecursion 0)

В боевых условиях используется 2000 :( Есть ли варианты? Или селектом никак?
28 авг 09, 11:02    [7589431]     Ответить | Цитировать Сообщить модератору
 Re: Степень по модулю  [new]
vino
Member

Откуда:
Сообщений: 1191
q111
Необходимо селектом вычислить степень числа по модулю (a^t)%m. Числа могут быть большие, поэтому использование power невозможно

Пока есть рекурсивный вариант для MS SQL 2005
with t1(a,t,m) as(select 2,5,29 union all select 6,4,23)

,t2 as(select m,t,a,k=t,c=a,b=1 from t1
union all
select m,t,a,
case when k%2=0 then k/2 else k-1 END,
case when k%2=0 then (c*c)%m else c end,
case when k%2=0 then b else (b*c)%m end
from t2 where k>0)

select a,t,m,b from t2 where k=0

option (maxrecursion 0)

В боевых условиях используется 2000 :( Есть ли варианты? Или селектом никак?

простой перевод в два селекта+цикл не подойдет?
28 авг 09, 12:35    [7590170]     Ответить | Цитировать Сообщить модератору
 Re: Степень по модулю  [new]
aleks2
Guest
q111,

Чем тебе UDF не угодила?
28 авг 09, 12:47    [7590237]     Ответить | Цитировать Сообщить модератору
 Re: Степень по модулю  [new]
q111
Guest
Нет, один селект
28 авг 09, 12:47    [7590241]     Ответить | Цитировать Сообщить модератору
 Re: Степень по модулю  [new]
iap
Member

Откуда: Москва
Сообщений: 46975
q111
Нет, один селект
Приведите диапазоны возможных значений a и t
28 авг 09, 12:49    [7590254]     Ответить | Цитировать Сообщить модератору
 Re: Степень по модулю  [new]
q111
Guest
автор
Приведите диапазоны возможных значений a и t

a,t,m - порядка bigint
a^t может превышать numeric(38)
28 авг 09, 13:07    [7590393]     Ответить | Цитировать Сообщить модератору
 Re: Степень по модулю  [new]
Алексей2003
Member

Откуда: Москва
Сообщений: 5645
q111
автор
Приведите диапазоны возможных значений a и t

a,t,m - порядка bigint
a^t может превышать numeric(38)

а вы уверены, что хотите такую задачу поручить SQL Server'у?
28 авг 09, 13:38    [7590649]     Ответить | Цитировать Сообщить модератору
 Re: Степень по модулю  [new]
q111
Guest
автор
а вы уверены, что хотите такую задачу поручить SQL Server'у?

А почему бы и нет, если это возможно.
Привык так: если можно задачу решить с помощью одного селект решаю, если невозможно то привлекаю средства t-sql, если и это невозможно то тогда уж udf... Пока же вопрос о том, что задача не решается одним селектом остается открытым. Пусть это будет пятничной задачей... ну так есть мысли?
28 авг 09, 13:45    [7590711]     Ответить | Цитировать Сообщить модератору
 Re: Степень по модулю  [new]
Maxx
Member [скрыт]

Откуда:
Сообщений: 24290
яб писал на чем нить более пригодном.. если 2000 то на каком нить с++ хранимку и цеплял..еслиб 2005 то CLR +C# вам в руки как раз самое оно
-------------------------------------
Jedem Das Seine
28 авг 09, 13:45    [7590712]     Ответить | Цитировать Сообщить модератору
 Re: Степень по модулю  [new]
Алексей2003
Member

Откуда: Москва
Сообщений: 5645
q111
автор
а вы уверены, что хотите такую задачу поручить SQL Server'у?

А почему бы и нет, если это возможно.
Привык так: если можно задачу решить с помощью одного селект решаю, если невозможно то привлекаю средства t-sql, если и это невозможно то тогда уж udf... Пока же вопрос о том, что задача не решается одним селектом остается открытым. Пусть это будет пятничной задачей... ну так есть мысли?

а m точно bitint может быть?
28 авг 09, 13:50    [7590731]     Ответить | Цитировать Сообщить модератору
 Re: Степень по модулю  [new]
Ozzy-Osbourne
Member

Откуда: Balashikha
Сообщений: 139
q111
почему бы и нет, если это возможно.
Вряд ли это возможно без рекурсии, даже в 2005.
Максимальное число для ваших условий = 9223372036854775807.
Для вычисления итога потребуется число итераций, равное 2*log2(9223372036854775807) = 126.
Вот самый большой запрос, который SS еще может выполнить (в нём заданы начальные m=9223372036854775807 и a=9223372036854775805):
  select top 999 m,t=case when t%2=0 then t/2 else t-1 end,a=(case when t>0 and t%2=0 then (a*a)%m else a end),x=case when t%2=0 then x else (a*x)%m end
  from(
  select top 999 m,t=case when t%2=0 then t/2 else t-1 end,a=(case when t>0 and t%2=0 then (a*a)%m else a end),x=case when t%2=0 then x else (a*x)%m end
  from(
  select top 999 m,t=case when t%2=0 then t/2 else t-1 end,a=(case when t>0 and t%2=0 then (a*a)%m else a end),x=case when t%2=0 then x else (a*x)%m end
  from(
  select top 999 m,t=case when t%2=0 then t/2 else t-1 end,a=(case when t>0 and t%2=0 then (a*a)%m else a end),x=case when t%2=0 then x else (a*x)%m end
  from(
  select top 999 m,t=case when t%2=0 then t/2 else t-1 end,a=(case when t>0 and t%2=0 then (a*a)%m else a end),x=case when t%2=0 then x else (a*x)%m end
  from(
  select top 999 m,t=case when t%2=0 then t/2 else t-1 end,a=(case when t>0 and t%2=0 then (a*a)%m else a end),x=case when t%2=0 then x else (a*x)%m end
  from(
  select top 999 m,t,a,x=cast(1 as numeric(38)) 
  from(select top 999 m=9223372036854775807, t=cast(9223372036854775807 as bigint), a=cast(9223372036854775805 as bigint)) t
  )s order by m,t,a,x 
  )s order by m,t,a,x 
  )s order by m,t,a,x 
  )s order by m,t,a,x 
  )s order by m,t,a,x 
  )s order by m,t,a,x 
При попытке сделать еще одну, всего лишь седьмую, итерацию появится сообщение
Msg 8632, Level 17, State 2, Line 1
Internal error: An expression services limit has been reached. Please look for potentially complex expressions in your query, and try to simplify them.


Попытки обойти это через СТЕ-шки (в надежде, что он там будет временные таблицы делать) не помогает, сообщение остается.
28 авг 09, 14:40    [7591075]     Ответить | Цитировать Сообщить модератору
 Re: Степень по модулю  [new]
iap
Member

Откуда: Москва
Сообщений: 46975
Я вот что думаю:


/*бином Ньютона */




так как все слагаемые, кроме случая t=k, делятся на m без остатка.

Я прав? Если да, то вместо
POWER(a,t)%m
можно писать
POWER(a%m,t)%m
Это Вам поможет?
28 авг 09, 14:41    [7591086]     Ответить | Цитировать Сообщить модератору
 Re: Степень по модулю  [new]
Ozzy-Osbourne
Member

Откуда: Balashikha
Сообщений: 139
2 iap: разумеется, никто не собирается возводить огромное число в огромную же степень! Но как сделать один НЕрекурсивный селект на всё это ?
28 авг 09, 14:59    [7591221]     Ответить | Цитировать Сообщить модератору
 Re: Степень по модулю  [new]
q111
Guest
Ozzy-Osbourne
Вряд ли это возможно без рекурсии, даже в 2005.
Максимальное число для ваших условий = 9223372036854775807.
Для вычисления итога потребуется число итераций, равное 2*log2(9223372036854775807) = 126.
Вот самый большой запрос, который SS еще может выполнить (в нём заданы начальные m=9223372036854775807 и a=9223372036854775805):

Ну это искусственная замена рекурсии - так уже тоже успел попробовать....

iap

Я прав? Если да, то вместо

POWER(a,t)%m

можно писать

POWER(a%m,t)%m

Это Вам поможет?

прав. И это поможет частично, когда а>m и можно уменьшить возводимое число, но степень то уменьшить никак.

Всем спасибо.Буду использовать циклы...
28 авг 09, 15:01    [7591237]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить