fork download
copy 
  1.  
  2. -- Линейный метод
  3. local function method1(b, e, m)
  4. 	local c = 1
  5. 	for i = 1, e do
  6. 		c = (c * b) % m
  7. 	end
  8.  
  9. 	return c
  10. end
  11.  
  12. -- Рекурсивный метод
  13. local function method2(b, e, m)
  14. 	if e == 0 then
  15. 		return 1
  16. 	elseif e == 1 then
  17. 		return b
  18. 	elseif e % 2 == 1 then
  19. 		return (method2(b, e - 1, m) * b) % m
  20. 	else
  21. 		local x = method2(b, e / 2, m)
  22. 		return (x * x) % m
  23. 	end
  24. end
  25.  
  26. -- Итеративный метод
  27. local function method3(b, e, m)
  28. 	local result = 1
  29. 	b = b % m
  30.  
  31. 	while e > 0 do
  32. 		if e % 2 == 1 then
  33. 			e, result = e - 1, (result * b) % m
  34. 		else
  35. 			e, b = e / 2, (b * b) % m
  36. 		end
  37. 	end
  38.  
  39. 	return result
  40. end
  41.  
  42. -- Итеративный метод с использованием бинарных операций
  43. local function method4(b, e, m)
  44. 	local result = 1
  45. 	b = b % m
  46.  
  47. 	while e > 0 do
  48. 		if e & 1 == 1 then
  49. 			result = (result * b) % m	
  50. 		end
  51.  
  52. 		e, b = e >> 1, (b * b) % m
  53. 	end
  54.  
  55. 	return result
  56. end
  57.  
  58. local function time(iterations, method, ...)
  59. 	local oldClock = os.clock()
  60. 	for i = 1, iterations do
  61. 		method(...)
  62. 	end
  63. 	print("Time: " .. string.format("%.8f", os.clock() - oldClock))
  64. end
  65.  
  66. time(50, method1, 2, 1000000, 37)
  67. time(50, method2, 2, 1000000, 37)
  68. time(50, method3, 2, 1000000, 37)
  69. time(50, method4, 2, 1000000, 37)
  70.  
Success #stdin #stdout 1.08s 4392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Time: 1.07760100
Time: 0.00020800
Time: 0.00010900
Time: 0.00006500
https://ideone.com/t9Yv5F
Modular exponentiation
language:
Lua (luac 5.3.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!