prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  where doesn't work with int16 and float64 on cuda6.5
  On only cuda 6.5, this code doesn't work:
  
  ```
  x = cupy.array([1,2,3], dtype=cupy.int16)
  y = cupy.array([1,2,3], dtype=cupy.float64)
  c = cupy.array([1,0,1], dtype=cupy.bool_)
  cupy.where(c, x, y)
  ```
  
  Other combinations such as (int16, float32) and (int32, float64) correctly work.
  Maybe this is a bug on cuda 6.5, and fixed on 7.0.
  
  Note that `cupy.where(c, y, x)` can work.
  
  
  </issue>
  <code>
  [start of cupy/sorting/search.py]
  1 from cupy import elementwise
  2 from cupy import reduction
  3 
  4 
  5 def argmax(a, axis=None, dtype=None, out=None, keepdims=False):
  6     """Returns the indices of the maximum along an axis.
  7 
  8     Args:
  9         a (cupy.ndarray): Array to take argmax.
  10         axis (int): Along which axis to find the maximum. ``a`` is flattened by
  11             default.
  12         dtype: Data type specifier.
  13         out (cupy.ndarray): Output array.
  14         keepdims (bool): If True, the axis ``axis`` is preserved as an axis of
  15             length one.
  16 
  17     Returns:
  18         cupy.ndarray: The indices of the maximum of ``a`` along an axis.
  19 
  20     .. seealso:: :func:`numpy.argmax`
  21 
  22     """
  23     return reduction.argmax(a, axis=axis, dtype=dtype, out=out,
  24                             keepdims=keepdims)
  25 
  26 
  27 # TODO(okuta): Implement nanargmax
  28 
  29 
  30 def argmin(a, axis=None, dtype=None, out=None, keepdims=False):
  31     """Returns the indices of the minimum along an axis.
  32 
  33     Args:
  34         a (cupy.ndarray): Array to take argmin.
  35         axis (int): Along which axis to find the minimum. ``a`` is flattened by
  36             default.
  37         dtype: Data type specifier.
  38         out (cupy.ndarray): Output array.
  39         keepdims (bool): If True, the axis ``axis`` is preserved as an axis of
  40             length one.
  41 
  42     Returns:
  43         cupy.ndarray: The indices of the minimum of ``a`` along an axis.
  44 
  45     .. seealso:: :func:`numpy.argmin`
  46 
  47     """
  48     return reduction.argmin(a, axis=axis, dtype=dtype, out=out,
  49                             keepdims=keepdims)
  50 
  51 
  52 # TODO(okuta): Implement nanargmin
  53 
  54 
  55 # TODO(okuta): Implement argwhere
  56 
  57 
  58 # TODO(okuta): Implement nonzero
  59 
  60 
  61 # TODO(okuta): Implement flatnonzero
  62 
  63 
  64 def where(condition, x=None, y=None):
  65     """Return elements, either from x or y, depending on condition.
  66 
  67     .. note::
  68 
  69        Currently Cupy doesn't support ``where(condition)``, that Numpy
  70        supports.
  71 
  72     Args:
  73         condition (cupy.ndarray): When True, take x, otherwise take y.
  74         x (cupy.ndarray): Values from which to choose on ``True``.
  75         y (cupy.ndarray): Values from which to choose on ``False``.
  76 
  77     Returns:
  78         cupy.ndarray: Each element of output contains elements of ``x`` when
  79             ``condition`` is ``True``, otherwise elements of ``y``.
  80 
  81     """
  82 
  83     missing = (x is None, y is None).count(True)
  84 
  85     if missing == 1:
  86         raise ValueError("Must provide both 'x' and 'y' or neither.")
  87     if missing == 2:
  88         # TODO(unno): return nonzero(cond)
  89         return NotImplementedError()
  90 
  91     return _where_ufunc(condition.astype('?'), x, y)
  92 
  93 _where_ufunc = elementwise.create_ufunc(
  94     'cupy_where',
  95     ('???->?', '?bb->b', '?BB->B', '?hh->h', '?HH->H', '?ii->i', '?II->I',
  96      '?ll->l', '?LL->L', '?qq->q', '?QQ->Q', '?ee->e', '?ff->f', '?dd->d'),
  97     'out0 = in0 ? in1 : in2')
  98 
  99 
  100 # TODO(okuta): Implement searchsorted
  101 
  102 
  103 # TODO(okuta): Implement extract
  104
  [end of cupy/sorting/search.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/cupy/sorting/search.py b/cupy/sorting/search.py
  --- a/cupy/sorting/search.py
  +++ b/cupy/sorting/search.py
  @@ -93,7 +93,12 @@
   _where_ufunc = elementwise.create_ufunc(
       'cupy_where',
       ('???->?', '?bb->b', '?BB->B', '?hh->h', '?HH->H', '?ii->i', '?II->I',
  -     '?ll->l', '?LL->L', '?qq->q', '?QQ->Q', '?ee->e', '?ff->f', '?dd->d'),
  +     '?ll->l', '?LL->L', '?qq->q', '?QQ->Q', '?ee->e', '?ff->f',
  +     # On CUDA 6.5 these combinations don't work correctly (on CUDA >=7.0, it
  +     # works).
  +     # See issue #551.
  +     '?hd->d', '?Hd->d',
  +     '?dd->d'),
       'out0 = in0 ? in1 : in2')
  
verification_info: {"golden_diff": "diff --git a/cupy/sorting/search.py b/cupy/sorting/search.py\n--- a/cupy/sorting/search.py\n+++ b/cupy/sorting/search.py\n@@ -93,7 +93,12 @@\n _where_ufunc = elementwise.create_ufunc(\n     'cupy_where',\n     ('???->?', '?bb->b', '?BB->B', '?hh->h', '?HH->H', '?ii->i', '?II->I',\n-     '?ll->l', '?LL->L', '?qq->q', '?QQ->Q', '?ee->e', '?ff->f', '?dd->d'),\n+     '?ll->l', '?LL->L', '?qq->q', '?QQ->Q', '?ee->e', '?ff->f',\n+     # On CUDA 6.5 these combinations don't work correctly (on CUDA >=7.0, it\n+     # works).\n+     # See issue #551.\n+     '?hd->d', '?Hd->d',\n+     '?dd->d'),\n     'out0 = in0 ? in1 : in2')\n", "issue": "where doesn't work with int16 and float64 on cuda6.5\nOn only cuda 6.5, this code doesn't work:\n\n```\nx = cupy.array([1,2,3], dtype=cupy.int16)\ny = cupy.array([1,2,3], dtype=cupy.float64)\nc = cupy.array([1,0,1], dtype=cupy.bool_)\ncupy.where(c, x, y)\n```\n\nOther combinations such as (int16, float32) and (int32, float64) correctly work.\nMaybe this is a bug on cuda 6.5, and fixed on 7.0.\n\nNote that `cupy.where(c, y, x)` can work.\n\n", "before_files": [{"content": "from cupy import elementwise\nfrom cupy import reduction\n\n\ndef argmax(a, axis=None, dtype=None, out=None, keepdims=False):\n    \"\"\"Returns the indices of the maximum along an axis.\n\n    Args:\n        a (cupy.ndarray): Array to take argmax.\n        axis (int): Along which axis to find the maximum. ``a`` is flattened by\n            default.\n        dtype: Data type specifier.\n        out (cupy.ndarray): Output array.\n        keepdims (bool): If True, the axis ``axis`` is preserved as an axis of\n            length one.\n\n    Returns:\n        cupy.ndarray: The indices of the maximum of ``a`` along an axis.\n\n    .. seealso:: :func:`numpy.argmax`\n\n    \"\"\"\n    return reduction.argmax(a, axis=axis, dtype=dtype, out=out,\n                            keepdims=keepdims)\n\n\n# TODO(okuta): Implement nanargmax\n\n\ndef argmin(a, axis=None, dtype=None, out=None, keepdims=False):\n    \"\"\"Returns the indices of the minimum along an axis.\n\n    Args:\n        a (cupy.ndarray): Array to take argmin.\n        axis (int): Along which axis to find the minimum. ``a`` is flattened by\n            default.\n        dtype: Data type specifier.\n        out (cupy.ndarray): Output array.\n        keepdims (bool): If True, the axis ``axis`` is preserved as an axis of\n            length one.\n\n    Returns:\n        cupy.ndarray: The indices of the minimum of ``a`` along an axis.\n\n    .. seealso:: :func:`numpy.argmin`\n\n    \"\"\"\n    return reduction.argmin(a, axis=axis, dtype=dtype, out=out,\n                            keepdims=keepdims)\n\n\n# TODO(okuta): Implement nanargmin\n\n\n# TODO(okuta): Implement argwhere\n\n\n# TODO(okuta): Implement nonzero\n\n\n# TODO(okuta): Implement flatnonzero\n\n\ndef where(condition, x=None, y=None):\n    \"\"\"Return elements, either from x or y, depending on condition.\n\n    .. note::\n\n       Currently Cupy doesn't support ``where(condition)``, that Numpy\n       supports.\n\n    Args:\n        condition (cupy.ndarray): When True, take x, otherwise take y.\n        x (cupy.ndarray): Values from which to choose on ``True``.\n        y (cupy.ndarray): Values from which to choose on ``False``.\n\n    Returns:\n        cupy.ndarray: Each element of output contains elements of ``x`` when\n            ``condition`` is ``True``, otherwise elements of ``y``.\n\n    \"\"\"\n\n    missing = (x is None, y is None).count(True)\n\n    if missing == 1:\n        raise ValueError(\"Must provide both 'x' and 'y' or neither.\")\n    if missing == 2:\n        # TODO(unno): return nonzero(cond)\n        return NotImplementedError()\n\n    return _where_ufunc(condition.astype('?'), x, y)\n\n_where_ufunc = elementwise.create_ufunc(\n    'cupy_where',\n    ('???->?', '?bb->b', '?BB->B', '?hh->h', '?HH->H', '?ii->i', '?II->I',\n     '?ll->l', '?LL->L', '?qq->q', '?QQ->Q', '?ee->e', '?ff->f', '?dd->d'),\n    'out0 = in0 ? in1 : in2')\n\n\n# TODO(okuta): Implement searchsorted\n\n\n# TODO(okuta): Implement extract\n", "path": "cupy/sorting/search.py"}]}