prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  Occasional test failure in `TestWalkerAlias`
  Occasionally, the result of `xp.random.uniform(0, 1, shape).astype(thr_dtype)` becomes `1.0`, and `self.threshold[index]` raises an `IndexError`.
  
  https://ci.appveyor.com/project/pfnet/chainer/builds/21769400/job/96weerl928ipapc6
  
  </issue>
  <code>
  [start of chainer/utils/walker_alias.py]
  1 import numpy
  2 
  3 import chainer
  4 from chainer import backend
  5 from chainer.backends import cuda
  6 
  7 
  8 class WalkerAlias(object):
  9     """Implementation of Walker's alias method.
  10 
  11     This method generates a random sample from given probabilities
  12     :math:`p_1, \\dots, p_n` in :math:`O(1)` time.
  13     It is more efficient than :func:`~numpy.random.choice`.
  14     This class works on both CPU and GPU.
  15 
  16     Args:
  17         probs (float list): Probabilities of entries. They are normalized with
  18                             `sum(probs)`.
  19 
  20     See: `Wikipedia article <https://en.wikipedia.org/wiki/Alias_method>`_
  21 
  22     """
  23 
  24     def __init__(self, probs):
  25         prob = numpy.array(probs, numpy.float32)
  26         prob /= numpy.sum(prob)
  27         threshold = numpy.ndarray(len(probs), numpy.float32)
  28         values = numpy.ndarray(len(probs) * 2, numpy.int32)
  29         il, ir = 0, 0
  30         pairs = list(zip(prob, range(len(probs))))
  31         pairs.sort()
  32         for prob, i in pairs:
  33             p = prob * len(probs)
  34             while p > 1 and ir < il:
  35                 values[ir * 2 + 1] = i
  36                 p -= 1.0 - threshold[ir]
  37                 ir += 1
  38             threshold[il] = p
  39             values[il * 2] = i
  40             il += 1
  41         # fill the rest
  42         for i in range(ir, len(probs)):
  43             values[i * 2 + 1] = 0
  44 
  45         assert((values < len(threshold)).all())
  46         self.threshold = threshold
  47         self.values = values
  48         self._device = backend.CpuDevice()
  49 
  50     @property
  51     def device(self):
  52         return self._device
  53 
  54     @property
  55     def use_gpu(self):
  56         # TODO(niboshi): Maybe better to deprecate the property.
  57         xp = self._device.xp
  58         if xp is cuda.cupy:
  59             return True
  60         elif xp is numpy:
  61             return False
  62         raise RuntimeError(
  63             'WalkerAlias.use_gpu attribute is only applicable for numpy or '
  64             'cupy devices. Use WalkerAlias.device attribute for general '
  65             'devices.')
  66 
  67     def to_device(self, device):
  68         device = chainer.get_device(device)
  69         self.threshold = device.send(self.threshold)
  70         self.values = device.send(self.values)
  71         self._device = device
  72         return self
  73 
  74     def to_gpu(self):
  75         """Make a sampler GPU mode.
  76 
  77         """
  78         return self.to_device(cuda.Device())
  79 
  80     def to_cpu(self):
  81         """Make a sampler CPU mode.
  82 
  83         """
  84         return self.to_device(backend.CpuDevice())
  85 
  86     def sample(self, shape):
  87         """Generates a random sample based on given probabilities.
  88 
  89         Args:
  90             shape (tuple of int): Shape of a return value.
  91 
  92         Returns:
  93             Returns a generated array with the given shape. If a sampler is in
  94             CPU mode the return value is a :class:`numpy.ndarray` object, and
  95             if it is in GPU mode the return value is a :class:`cupy.ndarray`
  96             object.
  97         """
  98         xp = self._device.xp
  99         with chainer.using_device(self._device):
  100             if xp is cuda.cupy:
  101                 return self.sample_gpu(shape)
  102             else:
  103                 return self.sample_xp(xp, shape)
  104 
  105     def sample_xp(self, xp, shape):
  106         thr_dtype = self.threshold.dtype
  107         ps = xp.random.uniform(0, 1, shape).astype(thr_dtype)
  108         pb = ps * len(self.threshold)
  109         index = pb.astype(numpy.int32)
  110         left_right = (
  111             self.threshold[index]
  112             < (pb - index.astype(thr_dtype)))
  113         left_right = left_right.astype(numpy.int32)
  114         return self.values[index * 2 + left_right]
  115 
  116     def sample_gpu(self, shape):
  117         ps = cuda.cupy.random.uniform(size=shape, dtype=numpy.float32)
  118         vs = cuda.elementwise(
  119             'T ps, raw T threshold , raw S values, int32 b',
  120             'int32 vs',
  121             '''
  122             T pb = ps * b;
  123             int index = __float2int_rd(pb);
  124             // fill_uniform sometimes returns 1.0, so we need to check index
  125             if (index >= b) {
  126               index = 0;
  127             }
  128             int lr = threshold[index] < pb - index;
  129             vs = values[index * 2 + lr];
  130             ''',
  131             'walker_alias_sample'
  132         )(ps, self.threshold, self.values, len(self.threshold))
  133         return vs
  134
  [end of chainer/utils/walker_alias.py]
  </code>
  
  I need you to solve this issue by generating a single patch file that I can apply directly to this repository using git apply. Please respond with a single patch file in the following format.
  <patch>
  diff --git a/file.py b/file.py
  --- a/file.py
  +++ b/file.py
  @@ -1,27 +1,35 @@
   def euclidean(a, b):
  -    while b:
  -        a, b = b, a % b
  -    return a
  +    if b == 0:
  +        return a
  +    return euclidean(b, a % b)
   
   
   def bresenham(x0, y0, x1, y1):
       points = []
       dx = abs(x1 - x0)
       dy = abs(y1 - y0)
  -    sx = 1 if x0 < x1 else -1
  -    sy = 1 if y0 < y1 else -1
  -    err = dx - dy
  +    x, y = x0, y0
  +    sx = -1 if x0 > x1 else 1
  +    sy = -1 if y0 > y1 else 1
   
  -    while True:
  -        points.append((x0, y0))
  -        if x0 == x1 and y0 == y1:
  -            break
  -        e2 = 2 * err
  -        if e2 > -dy:
  -            err -= dy
  -            x0 += sx
  -        if e2 < dx:
  -            err += dx
  -            y0 += sy
  +    if dx > dy:
  +        err = dx / 2.0
  +        while x != x1:
  +            points.append((x, y))
  +            err -= dy
  +            if err < 0:
  +                y += sy
  +                err += dx
  +            x += sx
  +    else:
  +        err = dy / 2.0
  +        while y != y1:
  +            points.append((x, y))
  +            err -= dx
  +            if err < 0:
  +                x += sx
  +                err += dy
  +            y += sy
  +
  +    points.append((x, y))
       return points
  
  </patch>
golden_diff: diff --git a/chainer/utils/walker_alias.py b/chainer/utils/walker_alias.py
  --- a/chainer/utils/walker_alias.py
  +++ b/chainer/utils/walker_alias.py
  @@ -104,12 +104,11 @@
   
       def sample_xp(self, xp, shape):
           thr_dtype = self.threshold.dtype
  -        ps = xp.random.uniform(0, 1, shape).astype(thr_dtype)
  -        pb = ps * len(self.threshold)
  +        pb = xp.random.uniform(0, len(self.threshold), shape)
           index = pb.astype(numpy.int32)
           left_right = (
               self.threshold[index]
  -            < (pb - index.astype(thr_dtype)))
  +            < (pb.astype(thr_dtype) - index.astype(thr_dtype)))
           left_right = left_right.astype(numpy.int32)
           return self.values[index * 2 + left_right]
  
verification_info: {"golden_diff": "diff --git a/chainer/utils/walker_alias.py b/chainer/utils/walker_alias.py\n--- a/chainer/utils/walker_alias.py\n+++ b/chainer/utils/walker_alias.py\n@@ -104,12 +104,11 @@\n \n     def sample_xp(self, xp, shape):\n         thr_dtype = self.threshold.dtype\n-        ps = xp.random.uniform(0, 1, shape).astype(thr_dtype)\n-        pb = ps * len(self.threshold)\n+        pb = xp.random.uniform(0, len(self.threshold), shape)\n         index = pb.astype(numpy.int32)\n         left_right = (\n             self.threshold[index]\n-            < (pb - index.astype(thr_dtype)))\n+            < (pb.astype(thr_dtype) - index.astype(thr_dtype)))\n         left_right = left_right.astype(numpy.int32)\n         return self.values[index * 2 + left_right]\n", "issue": "Occasional test failure in `TestWalkerAlias`\nOccasionally, the result of `xp.random.uniform(0, 1, shape).astype(thr_dtype)` becomes `1.0`, and `self.threshold[index]` raises an `IndexError`.\r\n\r\nhttps://ci.appveyor.com/project/pfnet/chainer/builds/21769400/job/96weerl928ipapc6\n", "before_files": [{"content": "import numpy\n\nimport chainer\nfrom chainer import backend\nfrom chainer.backends import cuda\n\n\nclass WalkerAlias(object):\n    \"\"\"Implementation of Walker's alias method.\n\n    This method generates a random sample from given probabilities\n    :math:`p_1, \\\\dots, p_n` in :math:`O(1)` time.\n    It is more efficient than :func:`~numpy.random.choice`.\n    This class works on both CPU and GPU.\n\n    Args:\n        probs (float list): Probabilities of entries. They are normalized with\n                            `sum(probs)`.\n\n    See: `Wikipedia article <https://en.wikipedia.org/wiki/Alias_method>`_\n\n    \"\"\"\n\n    def __init__(self, probs):\n        prob = numpy.array(probs, numpy.float32)\n        prob /= numpy.sum(prob)\n        threshold = numpy.ndarray(len(probs), numpy.float32)\n        values = numpy.ndarray(len(probs) * 2, numpy.int32)\n        il, ir = 0, 0\n        pairs = list(zip(prob, range(len(probs))))\n        pairs.sort()\n        for prob, i in pairs:\n            p = prob * len(probs)\n            while p > 1 and ir < il:\n                values[ir * 2 + 1] = i\n                p -= 1.0 - threshold[ir]\n                ir += 1\n            threshold[il] = p\n            values[il * 2] = i\n            il += 1\n        # fill the rest\n        for i in range(ir, len(probs)):\n            values[i * 2 + 1] = 0\n\n        assert((values < len(threshold)).all())\n        self.threshold = threshold\n        self.values = values\n        self._device = backend.CpuDevice()\n\n    @property\n    def device(self):\n        return self._device\n\n    @property\n    def use_gpu(self):\n        # TODO(niboshi): Maybe better to deprecate the property.\n        xp = self._device.xp\n        if xp is cuda.cupy:\n            return True\n        elif xp is numpy:\n            return False\n        raise RuntimeError(\n            'WalkerAlias.use_gpu attribute is only applicable for numpy or '\n            'cupy devices. Use WalkerAlias.device attribute for general '\n            'devices.')\n\n    def to_device(self, device):\n        device = chainer.get_device(device)\n        self.threshold = device.send(self.threshold)\n        self.values = device.send(self.values)\n        self._device = device\n        return self\n\n    def to_gpu(self):\n        \"\"\"Make a sampler GPU mode.\n\n        \"\"\"\n        return self.to_device(cuda.Device())\n\n    def to_cpu(self):\n        \"\"\"Make a sampler CPU mode.\n\n        \"\"\"\n        return self.to_device(backend.CpuDevice())\n\n    def sample(self, shape):\n        \"\"\"Generates a random sample based on given probabilities.\n\n        Args:\n            shape (tuple of int): Shape of a return value.\n\n        Returns:\n            Returns a generated array with the given shape. If a sampler is in\n            CPU mode the return value is a :class:`numpy.ndarray` object, and\n            if it is in GPU mode the return value is a :class:`cupy.ndarray`\n            object.\n        \"\"\"\n        xp = self._device.xp\n        with chainer.using_device(self._device):\n            if xp is cuda.cupy:\n                return self.sample_gpu(shape)\n            else:\n                return self.sample_xp(xp, shape)\n\n    def sample_xp(self, xp, shape):\n        thr_dtype = self.threshold.dtype\n        ps = xp.random.uniform(0, 1, shape).astype(thr_dtype)\n        pb = ps * len(self.threshold)\n        index = pb.astype(numpy.int32)\n        left_right = (\n            self.threshold[index]\n            < (pb - index.astype(thr_dtype)))\n        left_right = left_right.astype(numpy.int32)\n        return self.values[index * 2 + left_right]\n\n    def sample_gpu(self, shape):\n        ps = cuda.cupy.random.uniform(size=shape, dtype=numpy.float32)\n        vs = cuda.elementwise(\n            'T ps, raw T threshold , raw S values, int32 b',\n            'int32 vs',\n            '''\n            T pb = ps * b;\n            int index = __float2int_rd(pb);\n            // fill_uniform sometimes returns 1.0, so we need to check index\n            if (index >= b) {\n              index = 0;\n            }\n            int lr = threshold[index] < pb - index;\n            vs = values[index * 2 + lr];\n            ''',\n            'walker_alias_sample'\n        )(ps, self.threshold, self.values, len(self.threshold))\n        return vs\n", "path": "chainer/utils/walker_alias.py"}]}