Skip to content

Instantly share code, notes, and snippets.

@mizar

mizar/sagemath-divmod-issue.ipynb

Last active July 25, 2024 12:28
Show Gist options
  • Save mizar/07c293cb2a1ee4e896669335b99a6408 to your computer and use it in GitHub Desktop.
Save mizar/07c293cb2a1ee4e896669335b99a6408 to your computer and use it in GitHub Desktop.
Download ZIP
sagemath-divmod-issue.ipynb
Display the source blob
Display the rendered blob
Raw
sagemath-divmod-issue.ipynb
{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"provenance": [],
"authorship_tag": "ABX9TyPLIr+g892MYXsM0T0OYx86",
"include_colab_link": true
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3"
},
"language_info": {
"name": "python"
}
},
"cells": [
{
"cell_type": "markdown",
"metadata": {
"id": "view-in-github",
"colab_type": "text"
},
"source": [
"<a href=\"https://colab.research.google.com/gist/mizar/07c293cb2a1ee4e896669335b99a6408/sagemath-divmod-issue.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "EsN1KovqnF4z",
"outputId": "c35247d6-2ad9-429b-9a8d-47d6c4fb26a7"
},
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"\u001b[33m\r0% [Working]\u001b[0m\r \rHit:1 http://archive.ubuntu.com/ubuntu jammy InRelease\n",
"\u001b[33m\r0% [Waiting for headers] [Waiting for headers] [Connected to cloud.r-project.org (18.160.213.93)] [C\u001b[0m\r \rGet:2 http://archive.ubuntu.com/ubuntu jammy-updates InRelease [128 kB]\n",
"Get:3 http://security.ubuntu.com/ubuntu jammy-security InRelease [129 kB]\n",
"Hit:4 https://cloud.r-project.org/bin/linux/ubuntu jammy-cran40/ InRelease\n",
"Hit:5 https://developer.download.nvidia.com/compute/cuda/repos/ubuntu2204/x86_64 InRelease\n",
"Ign:6 https://r2u.stat.illinois.edu/ubuntu jammy InRelease\n",
"Hit:7 http://archive.ubuntu.com/ubuntu jammy-backports InRelease\n",
"Hit:8 https://r2u.stat.illinois.edu/ubuntu jammy Release\n",
"Hit:9 https://ppa.launchpadcontent.net/deadsnakes/ppa/ubuntu jammy InRelease\n",
"Hit:10 https://ppa.launchpadcontent.net/graphics-drivers/ppa/ubuntu jammy InRelease\n",
"Hit:11 https://ppa.launchpadcontent.net/ubuntugis/ppa/ubuntu jammy InRelease\n",
"Fetched 257 kB in 4s (71.8 kB/s)\n",
"Reading package lists... Done\n",
"Building dependency tree... Done\n",
"Reading state information... Done\n",
"49 packages can be upgraded. Run 'apt list --upgradable' to see them.\n",
"\u001b[1;33mW: \u001b[0mSkipping acquire of configured file 'main/source/Sources' as repository 'https://r2u.stat.illinois.edu/ubuntu jammy InRelease' does not seem to provide it (sources.list entry misspelt?)\u001b[0m\n",
"Reading package lists... Done\n",
"Building dependency tree... Done\n",
"Reading state information... Done\n",
"sagemath is already the newest version (9.5-4).\n",
"0 upgraded, 0 newly installed, 0 to remove and 49 not upgraded.\n"
]
}
],
"source": [
"# @title install SageMath\n",
"!apt update; apt install sagemath"
]
},
{
"cell_type": "code",
"source": [
"# @title Strange implementation of divmod(Rational,Integer)\n",
"# The quotient in Python divmod is floor_div.\n",
"# https://docs.python.org/3/library/functions.html#divmod\n",
"# The quotient in SageMath divmod is not guaranteed to take floor, and is not implemented for some types.\n",
"# https://github.com/sagemath/sage/blob/79c047c0a22a98bea4567d182c694fd4df1aea81/src/sage/structure/element.pyx#L2773-L2837\n",
"# In the case of NumPy, the quotient and remainder in the floor division are returned.\n",
"# https://numpy.org/doc/stable/reference/generated/numpy.divmod.html\n",
"!sage -c 'print(divmod(355/113,2))'\n",
"!sage -c 'print((355/113)//2)'\n",
"!sage -c 'print((355/113)%2)'\n",
"!sage -c 'print((355/113)/2)'\n",
"!sage -c 'print(floor((355/113)/2))'\n",
"!sage -c 'print((355/113)-floor((355/113)/2)*2)'\n"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "6QtSsyWMnOaM",
"outputId": "93003b19-8c6a-4361-f68c-2dfb88949f1f"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"(355/226, 0)\n",
"355/226\n",
"1\n",
"355/226\n",
"1\n",
"129/113\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"# @title Unimplemented of divmod(SymbolicRing,SymbolicRing)\n",
"!sage -c 'print(divmod(sqrt(3),sqrt(2)))'\n",
"!sage -c 'print(sqrt(3)//sqrt(2))'\n",
"!sage -c 'print(sqrt(3)%sqrt(2))'\n"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "bq96D3vepHG4",
"outputId": "6d98b176-c3e8-4a06-88ee-16a02f3f8cee"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"Traceback (most recent call last):\n",
" File \"/usr/bin/sage-eval\", line 10, in <module>\n",
" eval(compile(s,'<cmdline>','exec'))\n",
" File \"<cmdline>\", line 1, in <module>\n",
"TypeError: unsupported operand type(s) for divmod(): 'sage.symbolic.expression.Expression' and 'sage.symbolic.expression.Expression'\n",
"Traceback (most recent call last):\n",
" File \"sage/structure/element.pyx\", line 1870, in sage.structure.element.Element._floordiv_ (build/cythonized/sage/structure/element.c:13911)\n",
" File \"sage/structure/element.pyx\", line 494, in sage.structure.element.Element.__getattr__ (build/cythonized/sage/structure/element.c:4827)\n",
" File \"sage/structure/element.pyx\", line 507, in sage.structure.element.Element.getattr_from_category (build/cythonized/sage/structure/element.c:4939)\n",
" File \"sage/cpython/getattr.pyx\", line 361, in sage.cpython.getattr.getattr_from_other_class (build/cythonized/sage/cpython/getattr.c:2703)\n",
"AttributeError: 'sage.symbolic.ring.SymbolicRing' object has no attribute '__custom_name'\n",
"\n",
"During handling of the above exception, another exception occurred:\n",
"\n",
"Traceback (most recent call last):\n",
" File \"/usr/bin/sage-eval\", line 10, in <module>\n",
" eval(compile(s,'<cmdline>','exec'))\n",
" File \"<cmdline>\", line 1, in <module>\n",
" File \"sage/structure/element.pyx\", line 1837, in sage.structure.element.Element.__floordiv__ (build/cythonized/sage/structure/element.c:13687)\n",
" File \"sage/structure/element.pyx\", line 1872, in sage.structure.element.Element._floordiv_ (build/cythonized/sage/structure/element.c:13983)\n",
"TypeError: unsupported operand parent(s) for //: 'Symbolic Ring' and 'Symbolic Ring'\n",
"Traceback (most recent call last):\n",
" File \"sage/structure/element.pyx\", line 1970, in sage.structure.element.Element._mod_ (build/cythonized/sage/structure/element.c:14324)\n",
" File \"sage/structure/element.pyx\", line 494, in sage.structure.element.Element.__getattr__ (build/cythonized/sage/structure/element.c:4827)\n",
" File \"sage/structure/element.pyx\", line 507, in sage.structure.element.Element.getattr_from_category (build/cythonized/sage/structure/element.c:4939)\n",
" File \"sage/cpython/getattr.pyx\", line 361, in sage.cpython.getattr.getattr_from_other_class (build/cythonized/sage/cpython/getattr.c:2703)\n",
"AttributeError: 'sage.symbolic.ring.SymbolicRing' object has no attribute '__custom_name'\n",
"\n",
"During handling of the above exception, another exception occurred:\n",
"\n",
"Traceback (most recent call last):\n",
" File \"/usr/bin/sage-eval\", line 10, in <module>\n",
" eval(compile(s,'<cmdline>','exec'))\n",
" File \"<cmdline>\", line 1, in <module>\n",
" File \"sage/structure/element.pyx\", line 1937, in sage.structure.element.Element.__mod__ (build/cythonized/sage/structure/element.c:14100)\n",
" File \"sage/structure/element.pyx\", line 1972, in sage.structure.element.Element._mod_ (build/cythonized/sage/structure/element.c:14396)\n",
"TypeError: unsupported operand parent(s) for %: 'Symbolic Ring' and 'Symbolic Ring'\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"# @title Example of how to avoid the problem of divmod\n",
"!sage -c 'print(sqrt(3)/sqrt(2))'\n",
"!sage -c 'print(floor(sqrt(3)/sqrt(2)))'\n",
"!sage -c 'print(sqrt(3)-floor(sqrt(3)/sqrt(2))*sqrt(2))'"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "6K46quA_wdH5",
"outputId": "b37123d1-1c6d-4442-ea45-5fa6fd98fe22"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"1/2*sqrt(3)*sqrt(2)\n",
"1\n",
"sqrt(3) - sqrt(2)\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"# @title Behavior of divmod in case of Sympy\n",
"import sympy\n",
"print(divmod(sympy.Rational(355,113),2))\n",
"print(sympy.Rational(355,113)//2)\n",
"print(sympy.Rational(355,113)%2)\n",
"print(sympy.Rational(355,113)/2)\n",
"print(sympy.floor(sympy.Rational(355,113)/2))\n",
"print(sympy.Rational(355,113)-sympy.floor(sympy.Rational(355,113)/2)*2)\n",
"print(divmod(sympy.sqrt(3),sympy.sqrt(2)))\n",
"print(sympy.sqrt(3)//sympy.sqrt(2))\n",
"print(sympy.sqrt(3)%sympy.sqrt(2))\n",
"print(sympy.sqrt(3)/sympy.sqrt(2))\n",
"print(sympy.floor(sympy.sqrt(3)/sympy.sqrt(2)))\n",
"print(sympy.sqrt(3)-sympy.floor(sympy.sqrt(3)/sympy.sqrt(2))*sympy.sqrt(2))\n"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "J0hgYh2roMyy",
"outputId": "79ecfb8d-a41e-4393-99a8-899df5bd1b0d"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"(1, 129/113)\n",
"1\n",
"129/113\n",
"355/226\n",
"1\n",
"129/113\n",
"(1, -sqrt(2) + sqrt(3))\n",
"1\n",
"-sqrt(2) + sqrt(3)\n",
"sqrt(6)/2\n",
"1\n",
"-sqrt(2) + sqrt(3)\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"# @title Example of divmod: Sum of Floor of Linear taking real numbers as parameters\n",
"\n",
"def floor_sum(n, m, a, b, x=0): # calc sum_{i=0}^{n-1} floor((ai + b) / m)\n",
" while n!=0:(s,m),(t,u),a=divmod(a,m),divmod(b,m),m;x+=(n*n-n)//2*s+n*t;n,b=divmod(m*n+u,a)\n",
" return x\n",
"\n",
"import sympy\n",
"print(floor_sum(2**64,1,3,0))\n",
"print(floor_sum(2**64,1,sympy.Rational(355,113),0))\n",
"print(floor_sum(2**64,1,sympy.sqrt(10),0))\n"
],
"metadata": {
"id": "uNrqBqWv2SKo",
"outputId": "0d4fd1af-2e99-49a0-af2e-e726f66f1022",
"colab": {
"base_uri": "https://localhost:8080/"
}
},
"execution_count": 1,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"510423550381407695167391795037087989760\n",
"534514337420058205844616620158652010894\n",
"538033663531651603400662643251823957383\n"
]
}
]
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment