prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  backward of F.normalize is not stable
  `NormalizeL2.backward` computes 0/0 if the input contains a zero vector.  PR #4190, I wrote, caused this.  Sorry.
  
  To begin with, x/(||x|| + eps) is C^1 but not C^2 (at x=0).  The correct backward might not be a good choice.
  
  </issue>
  <code>
  [start of chainer/functions/normalization/l2_normalization.py]
  1 import numpy
  2 
  3 from chainer.backends import cuda
  4 from chainer import function_node
  5 import chainer.functions
  6 from chainer import utils
  7 from chainer.utils import type_check
  8 
  9 
  10 class NormalizeL2(function_node.FunctionNode):
  11 
  12     """L2 normalization"""
  13 
  14     def __init__(self, eps=1e-5, axis=1):
  15         self.eps = eps
  16         if isinstance(axis, int):
  17             axis = axis,
  18         self.axis = axis
  19 
  20     def check_type_forward(self, in_types):
  21         type_check.expect(in_types.size() == 1)
  22         x_type, = in_types
  23 
  24         type_check.expect(
  25             x_type.dtype == numpy.float32,
  26         )
  27 
  28     def forward(self, inputs):
  29         self.retain_inputs((0,))
  30         x, = inputs
  31         xp = cuda.get_array_module(x)
  32         norm = (xp.sqrt(xp.sum(xp.square(x), axis=self.axis, keepdims=True))
  33                 + x.dtype.type(self.eps))
  34         return utils.force_array(x / norm),
  35 
  36     def backward(self, indexes, grad_outputs):
  37         x, = self.get_retained_inputs()
  38         gy, = grad_outputs
  39         F = chainer.functions
  40 
  41         norm_noeps = F.sqrt(F.sum(F.square(x), axis=self.axis, keepdims=True))
  42         norm = norm_noeps + self.eps
  43         norm = F.broadcast_to(norm, gy.shape)
  44 
  45         x_gy_reduced = F.sum((x * gy), axis=self.axis, keepdims=True)
  46         x_gy_reduced /= norm_noeps
  47         x_gy_reduced = F.broadcast_to(x_gy_reduced, gy.shape)
  48         gx = gy * norm - x_gy_reduced * x
  49         gx = gx / norm ** 2
  50 
  51         return gx,
  52 
  53 
  54 def normalize(x, eps=1e-5, axis=1):
  55     """L2 norm squared (a.k.a.\\  Euclidean norm).
  56 
  57     This function implements L2 normalization on a vector along the given axis.
  58     No reduction is done along the normalization axis.
  59 
  60     In the case when :obj:`axis=1` and :math:`\\mathbf{x}` is a matrix of
  61     dimension :math:`(N, K)`, where :math:`N` and :math:`K` denote mini-batch
  62     size and the dimension of the input vectors, this function computes an
  63     output matrix :math:`\\mathbf{y}` of dimension :math:`(N, K)` by the
  64     following equation:
  65 
  66     .. math::
  67        \\mathbf{y}_i =
  68            {\\mathbf{x}_i \\over \\| \\mathbf{x}_i \\|_2 + \\epsilon}
  69 
  70     :obj:`eps` is used to avoid division by zero when norm of
  71     :math:`\\mathbf{x}` along the given axis is zero.
  72 
  73     The default value of :obj:`axis` is determined for backward compatibility.
  74 
  75     Args:
  76         x (~chainer.Variable): Two dimensional output variable. The first
  77             dimension is assumed to be the mini-batch dimension.
  78         eps (float): Epsilon value for numerical stability.
  79         axis (int or tuple of ints): Axis along which to normalize.
  80 
  81     Returns:
  82         ~chainer.Variable: The output variable which has the same shape
  83         as :math:`x`.
  84 
  85     """
  86     return NormalizeL2(eps, axis).apply((x,))[0]
  87
  [end of chainer/functions/normalization/l2_normalization.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/functions/normalization/l2_normalization.py b/chainer/functions/normalization/l2_normalization.py
  --- a/chainer/functions/normalization/l2_normalization.py
  +++ b/chainer/functions/normalization/l2_normalization.py
  @@ -7,6 +7,25 @@
   from chainer.utils import type_check
   
   
  +class _SetItemZero(function_node.FunctionNode):
  +
  +    """Write values to mask of zero-initialized array"""
  +
  +    def __init__(self, mask):
  +        self.mask = mask
  +
  +    def forward(self, inputs):
  +        x, = inputs
  +        xp = cuda.get_array_module(x)
  +        y = xp.zeros(self.mask.shape, x.dtype)
  +        y[self.mask] = x
  +        return y,
  +
  +    def backward(self, indices, grad_outputs):
  +        g, = grad_outputs
  +        return g[self.mask],
  +
  +
   class NormalizeL2(function_node.FunctionNode):
   
       """L2 normalization"""
  @@ -43,7 +62,14 @@
           norm = F.broadcast_to(norm, gy.shape)
   
           x_gy_reduced = F.sum((x * gy), axis=self.axis, keepdims=True)
  -        x_gy_reduced /= norm_noeps
  +
  +        # L2 normalize with eps has continuous backward. However,
  +        # the backward is not differentiable for the indices of zero vectors.
  +        # To avoid nan in double backward, do not compute outside of mask.
  +        mask = norm_noeps.array != 0
  +        x_gy_reduced, = _SetItemZero(mask).apply((
  +            x_gy_reduced[mask] / norm_noeps[mask],))
  +
           x_gy_reduced = F.broadcast_to(x_gy_reduced, gy.shape)
           gx = gy * norm - x_gy_reduced * x
           gx = gx / norm ** 2
  
verification_info: {"golden_diff": "diff --git a/chainer/functions/normalization/l2_normalization.py b/chainer/functions/normalization/l2_normalization.py\n--- a/chainer/functions/normalization/l2_normalization.py\n+++ b/chainer/functions/normalization/l2_normalization.py\n@@ -7,6 +7,25 @@\n from chainer.utils import type_check\n \n \n+class _SetItemZero(function_node.FunctionNode):\n+\n+    \"\"\"Write values to mask of zero-initialized array\"\"\"\n+\n+    def __init__(self, mask):\n+        self.mask = mask\n+\n+    def forward(self, inputs):\n+        x, = inputs\n+        xp = cuda.get_array_module(x)\n+        y = xp.zeros(self.mask.shape, x.dtype)\n+        y[self.mask] = x\n+        return y,\n+\n+    def backward(self, indices, grad_outputs):\n+        g, = grad_outputs\n+        return g[self.mask],\n+\n+\n class NormalizeL2(function_node.FunctionNode):\n \n     \"\"\"L2 normalization\"\"\"\n@@ -43,7 +62,14 @@\n         norm = F.broadcast_to(norm, gy.shape)\n \n         x_gy_reduced = F.sum((x * gy), axis=self.axis, keepdims=True)\n-        x_gy_reduced /= norm_noeps\n+\n+        # L2 normalize with eps has continuous backward. However,\n+        # the backward is not differentiable for the indices of zero vectors.\n+        # To avoid nan in double backward, do not compute outside of mask.\n+        mask = norm_noeps.array != 0\n+        x_gy_reduced, = _SetItemZero(mask).apply((\n+            x_gy_reduced[mask] / norm_noeps[mask],))\n+\n         x_gy_reduced = F.broadcast_to(x_gy_reduced, gy.shape)\n         gx = gy * norm - x_gy_reduced * x\n         gx = gx / norm ** 2\n", "issue": "backward of F.normalize is not stable\n`NormalizeL2.backward` computes 0/0 if the input contains a zero vector.  PR #4190, I wrote, caused this.  Sorry.\r\n\r\nTo begin with, x/(||x|| + eps) is C^1 but not C^2 (at x=0).  The correct backward might not be a good choice.\n", "before_files": [{"content": "import numpy\n\nfrom chainer.backends import cuda\nfrom chainer import function_node\nimport chainer.functions\nfrom chainer import utils\nfrom chainer.utils import type_check\n\n\nclass NormalizeL2(function_node.FunctionNode):\n\n    \"\"\"L2 normalization\"\"\"\n\n    def __init__(self, eps=1e-5, axis=1):\n        self.eps = eps\n        if isinstance(axis, int):\n            axis = axis,\n        self.axis = axis\n\n    def check_type_forward(self, in_types):\n        type_check.expect(in_types.size() == 1)\n        x_type, = in_types\n\n        type_check.expect(\n            x_type.dtype == numpy.float32,\n        )\n\n    def forward(self, inputs):\n        self.retain_inputs((0,))\n        x, = inputs\n        xp = cuda.get_array_module(x)\n        norm = (xp.sqrt(xp.sum(xp.square(x), axis=self.axis, keepdims=True))\n                + x.dtype.type(self.eps))\n        return utils.force_array(x / norm),\n\n    def backward(self, indexes, grad_outputs):\n        x, = self.get_retained_inputs()\n        gy, = grad_outputs\n        F = chainer.functions\n\n        norm_noeps = F.sqrt(F.sum(F.square(x), axis=self.axis, keepdims=True))\n        norm = norm_noeps + self.eps\n        norm = F.broadcast_to(norm, gy.shape)\n\n        x_gy_reduced = F.sum((x * gy), axis=self.axis, keepdims=True)\n        x_gy_reduced /= norm_noeps\n        x_gy_reduced = F.broadcast_to(x_gy_reduced, gy.shape)\n        gx = gy * norm - x_gy_reduced * x\n        gx = gx / norm ** 2\n\n        return gx,\n\n\ndef normalize(x, eps=1e-5, axis=1):\n    \"\"\"L2 norm squared (a.k.a.\\\\  Euclidean norm).\n\n    This function implements L2 normalization on a vector along the given axis.\n    No reduction is done along the normalization axis.\n\n    In the case when :obj:`axis=1` and :math:`\\\\mathbf{x}` is a matrix of\n    dimension :math:`(N, K)`, where :math:`N` and :math:`K` denote mini-batch\n    size and the dimension of the input vectors, this function computes an\n    output matrix :math:`\\\\mathbf{y}` of dimension :math:`(N, K)` by the\n    following equation:\n\n    .. math::\n       \\\\mathbf{y}_i =\n           {\\\\mathbf{x}_i \\\\over \\\\| \\\\mathbf{x}_i \\\\|_2 + \\\\epsilon}\n\n    :obj:`eps` is used to avoid division by zero when norm of\n    :math:`\\\\mathbf{x}` along the given axis is zero.\n\n    The default value of :obj:`axis` is determined for backward compatibility.\n\n    Args:\n        x (~chainer.Variable): Two dimensional output variable. The first\n            dimension is assumed to be the mini-batch dimension.\n        eps (float): Epsilon value for numerical stability.\n        axis (int or tuple of ints): Axis along which to normalize.\n\n    Returns:\n        ~chainer.Variable: The output variable which has the same shape\n        as :math:`x`.\n\n    \"\"\"\n    return NormalizeL2(eps, axis).apply((x,))[0]\n", "path": "chainer/functions/normalization/l2_normalization.py"}]}