fork(2) download
copy 
  1. def unsigned_div_newton(a, b):
  2.     assert a >= 0 and b > 0
  3.     if a <= b:
  4.         return int(a == b)
  5.  
  6.     k = a.bit_length() + b.bit_length()  # a*b < 2**k
  7.     x = 2  #  0 < x < 2**(k+1)/b  # initial guess for convergence
  8.     lastx = None
  9.     while lastx != x:
  10.         lastx = x
  11.         x = (x * (2**(k + 1) - x * b)) >> k
  12.     if x*b < 2**k: 
  13.         x += 1
  14.     return (a * x) >> k
  15.  
  16. import sys
  17. print(unsigned_div_newton(*map(int, sys.stdin)))
Success #stdin #stdout 0.04s 9604KB
comments (?)
stdin
copy 
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
2
stdout
copy 
5357543035931336604742125245300009052807024058527668037218751941851755255624680612465991894078479290637973364587765734125935726428461570217992288787349287401967283887412115492710537302531185570938977091076523237491790970633699383779582771973038531457285598238843271083830214915826312193418602834034688
https://ideone.com/ZNR9Eo
language:
Python 3 (python  3.12)
created:
8 years ago
visibility:
secret

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!