{"id":251,"date":"2016-10-26T11:28:42","date_gmt":"2016-10-26T11:28:42","guid":{"rendered":"http:\/\/bacon.umcs.lublin.pl\/~wolsk\/?page_id=251"},"modified":"2024-04-23T18:57:44","modified_gmt":"2024-04-23T18:57:44","slug":"human-problem-solving","status":"publish","type":"page","link":"https:\/\/bacon.umcs.lublin.pl\/~wolsk\/?page_id=251","title":{"rendered":"Human Problem Solving"},"content":{"rendered":"<pre>http:\/\/mirror.us-midwest-1.nexcess.net\/gnu\/emacs\/windows\/emacs-27\/\n\nhttp:\/\/www.sbcl.org\/platform-table.html\n\nhttps:\/\/www.quicklisp.org\/beta\/\n\nTo get started with the Quicklisp beta, \ndownload and load https:\/\/beta.quicklisp.org\/quicklisp.lisp\n\n\nC:\\Users\\maart&gt;cd c:\\home\n\nc:\\home&gt;sbcl --load quicklisp.lisp\n\n ==== quicklisp quickstart 2015-01-28 loaded ====\n\n    To continue with installation, evaluate: \n\n0] (quicklisp-quickstart:install)\n\n\n ==== quicklisp installed ====\n\n    To load a system, use: (ql:quickload \"system-name\")\n\n    To find systems, use: (ql:system-apropos \"term\")\n\n    To load Quicklisp every time you start Lisp, use: (ql:add-to-init-file)\n\n    For more information, see http:\/\/www.quicklisp.org\/beta\/\n\nNIL\n0] (ql:add-to-init-file)\n\n\n\n\nI will append the following lines to #P\"C:\/home\/.sbclrc\":\n\n  ;;; The following lines added by ql:add-to-init-file:\n  #-quicklisp\n  (let ((quicklisp-init (merge-pathnames \"quicklisp\/setup.lisp\"\n                                         (user-homedir-pathname))))\n    (when (probe-file quicklisp-init)\n      (load quicklisp-init)))\n\nPress Enter to continue.\n\n0] (ql:quickload \"quicklisp-slime-helper\")\n\n\nTo use, add this to your ~\/.emacs:\n\n  (load (expand-file-name \"~\/quicklisp\/slime-helper.el\"))\n  ;; Replace \"sbcl\" with the path to your implementation\n  (setq inferior-lisp-program \"sbcl\")\n\n\n(\"quicklisp-slime-helper\")\n0]\n\n\nPS C:\\Users\\maart\\2020-IT&gt; Get-Content C:\\home\\.emacs\n(load (expand-file-name \"~\/quicklisp\/slime-helper.el\"))\n;; Replace \"sbcl\" with the path to your implementation\n(setq inferior-lisp-program \"sbcl\")\n<\/pre>\n<h2><strong>Alternative Installation from Linux (Widnows-Subsystem)<\/strong><\/h2>\n<pre>1.     Open PowerShell as Administrator and run:\n\nEnable-WindowsOptionalFeature -Online -FeatureName Microsoft-Windows-Subsystem-Linux\n\n2.     Restart your computer when prompted.\n\n\n\n<\/pre>\n<h2><strong> Installation on Fedora<\/strong><\/h2>\n<pre>[maarten@localhost ~]$ wget https:\/\/beta.quicklisp.org\/quicklisp.lisp\n--2020-10-15 14:47:55--  https:\/\/beta.quicklisp.org\/quicklisp.lisp\nResolving beta.quicklisp.org (beta.quicklisp.org)... 13.225.78.17, 13.225.78.33, 13.225.78.81, ...\nConnecting to beta.quicklisp.org (beta.quicklisp.org)|13.225.78.17|:443... connected.\nHTTP request sent, awaiting response... 200 OK\nLength: 57144 (56K) [text\/plain]\nSaving to: \u2018quicklisp.lisp\u2019\n\nquicklisp.lisp      100%[===================&gt;]  55.80K  --.-KB\/s    in 0.06s   \n\n2020-10-15 14:47:57 (869 KB\/s) - \u2018quicklisp.lisp\u2019 saved [57144\/57144]\n\n[maarten@localhost ~]$ sbcl --load quicklisp.lisp\nThis is SBCL 1.4.6-1.fc28, an implementation of ANSI Common Lisp.\nMore information about SBCL is available at &lt;http:\/\/www.sbcl.org\/&gt;.\n\nSBCL is free software, provided as is, with absolutely no warranty.\nIt is mostly in the public domain; some portions are provided under\nBSD-style licenses.  See the CREDITS and COPYING files in the\ndistribution for more information.\n\n  ==== quicklisp quickstart 2015-01-28 loaded ====\n\n    To continue with installation, evaluate: (quicklisp-quickstart:install)\n\n    For installation options, evaluate: (quicklisp-quickstart:help)\n\n* (quicklisp-quickstart:install)\n\n; Fetching #&lt;URL \"http:\/\/beta.quicklisp.org\/client\/quicklisp.sexp\"&gt;\n; 0.82KB\n==================================================\n838 bytes in 0.00 seconds (0.00KB\/sec)\n; Fetching #&lt;URL \"http:\/\/beta.quicklisp.org\/client\/2020-01-04\/quicklisp.tar\"&gt;\n; 250.00KB\n==================================================\n256,000 bytes in 0.18 seconds (1404.49KB\/sec)\n; Fetching #&lt;URL \"http:\/\/beta.quicklisp.org\/client\/2015-09-24\/setup.lisp\"&gt;\n; 4.94KB\n==================================================\n5,054 bytes in 0.00 seconds (4935.55KB\/sec)\n; Fetching #&lt;URL \"http:\/\/beta.quicklisp.org\/asdf\/2.26\/asdf.lisp\"&gt;\n; 194.07KB\n==================================================\n198,729 bytes in 0.16 seconds (1228.30KB\/sec)\n; Fetching #&lt;URL \"http:\/\/beta.quicklisp.org\/dist\/quicklisp.txt\"&gt;\n; 0.40KB\n==================================================\n408 bytes in 0.00 seconds (398.44KB\/sec)\nInstalling dist \"quicklisp\" version \"2020-09-25\".\n; Fetching #&lt;URL \"http:\/\/beta.quicklisp.org\/dist\/quicklisp\/2020-09-25\/releases.txt\"&gt;\n; 465.71KB\n==================================================\n476,886 bytes in 0.25 seconds (1826.31KB\/sec)\n; Fetching #&lt;URL \"http:\/\/beta.quicklisp.org\/dist\/quicklisp\/2020-09-25\/systems.txt\"&gt;\n; 339.84KB\n==================================================\n347,992 bytes in 0.21 seconds (1626.01KB\/sec)\n\n  ==== quicklisp installed ====\n\n    To load a system, use: (ql:quickload \"system-name\")\n\n    To find systems, use: (ql:system-apropos \"term\")\n\n    To load Quicklisp every time you start Lisp, use: (ql:add-to-init-file)\n\n    For more information, see http:\/\/www.quicklisp.org\/beta\/\n\nNIL\n* (ql:add-to-init-file)\nI will append the following lines to #P\"\/home\/maarten\/.sbclrc\":\n\n  ;;; The following lines added by ql:add-to-init-file:\n  #-quicklisp\n  (let ((quicklisp-init (merge-pathnames \"quicklisp\/setup.lisp\"\n                                         (user-homedir-pathname))))\n    (when (probe-file quicklisp-init)\n      (load quicklisp-init)))\n\nPress Enter to continue.\n\n\n#P\"\/home\/maarten\/.sbclrc\"\n* (ql:quickload \"quicklisp-slime-helper\")\nTo load \"quicklisp-slime-helper\":\n  Load 1 ASDF system:\n    asdf\n  Install 3 Quicklisp releases:\n    alexandria quicklisp-slime-helper slime\n; Fetching #&lt;URL \"http:\/\/beta.quicklisp.org\/archive\/slime\/2020-09-25\/slime-v2.26.tgz\"&gt;\n; 802.88KB\n==================================================\n822,146 bytes in 0.38 seconds (2141.01KB\/sec)\n; Fetching #&lt;URL \"http:\/\/beta.quicklisp.org\/archive\/alexandria\/2020-09-25\/alexandria-20200925-git.tgz\"&gt;\n; 53.45KB\n==================================================\n54,730 bytes in 0.07 seconds (752.78KB\/sec)\n; Fetching #&lt;URL \"http:\/\/beta.quicklisp.org\/archive\/quicklisp-slime-helper\/2015-07-09\/quicklisp-slime-helper-20150709-git.tgz\"&gt;\n; 2.16KB\n==================================================\n2,211 bytes in 0.00 seconds (0.00KB\/sec)\n; Loading \"quicklisp-slime-helper\"\n[package swank-loader]............................\n[package swank\/backend]..........................\n[package swank\/rpc]...............................\n[package swank\/match].............................\n[package swank-mop]..............................\n[package swank]..................................\n[package swank\/source-path-parser]................\n[package swank\/source-file-cache].................\n[package swank\/sbcl].............................\n[package swank\/gray]..............................\n.........\n; compiling file \"\/home\/maarten\/quicklisp\/dists\/quicklisp\/software\/slime-v2.26\/contrib\/swank-util.lisp\" (written 15 OCT 2020 02:50:13 PM):\n.\n\n; \/home\/maarten\/.slime\/fasl\/2.26\/sbcl-1.4.6-1.fc28-linux-x86-64\/contrib\/swank-util.fasl written\n; compilation finished in 0:00:00.024\n; compiling file \"\/home\/maarten\/quicklisp\/dists\/quicklisp\/software\/slime-v2.26\/contrib\/swank-repl.lisp\" (written 15 OCT 2020 02:50:13 PM):\n.......................................\n[package swank-repl]..\n\n; \/home\/maarten\/.slime\/fasl\/2.26\/sbcl-1.4.6-1.fc28-linux-x86-64\/contrib\/swank-repl.fasl written\n; compilation finished in 0:00:00.083\n; compiling file \"\/home\/maarten\/quicklisp\/dists\/quicklisp\/software\/slime-v2.26\/contrib\/swank-c-p-c.lisp\" (written 15 OCT 2020 02:50:13 PM):\n.\n\n; \/home\/maarten\/.slime\/fasl\/2.26\/sbcl-1.4.6-1.fc28-linux-x86-64\/contrib\/swank-c-p-c.fasl written\n; compilation finished in 0:00:00.062\n; compiling file \"\/home\/maarten\/quicklisp\/dists\/quicklisp\/software\/slime-v2.26\/contrib\/swank-arglists.lisp\" (written 15 OCT 2020 02:50:13 PM):\n................\n\n; \/home\/maarten\/.slime\/fasl\/2.26\/sbcl-1.4.6-1.fc28-linux-x86-64\/contrib\/swank-arglists.fasl written\n; compilation finished in 0:00:00.712\n; compiling file \"\/home\/maarten\/quicklisp\/dists\/quicklisp\/software\/slime-v2.26\/contrib\/swank-fuzzy.lisp\" (written 15 OCT 2020 02:50:13 PM):\n...\n\n; \/home\/maarten\/.slime\/fasl\/2.26\/sbcl-1.4.6-1.fc28-linux-x86-64\/contrib\/swank-fuzzy.fasl written\n; compilation finished in 0:00:00.145\n; compiling file \"\/home\/maarten\/quicklisp\/dists\/quicklisp\/software\/slime-v2.26\/contrib\/swank-fancy-inspector.lisp\" (written 15 OCT 2020 02:50:13 PM):\n........\n\n; \/home\/maarten\/.slime\/fasl\/2.26\/sbcl-1.4.6-1.fc28-linux-x86-64\/contrib\/swank-fancy-inspector.fasl written\n; compilation finished in 0:00:00.322\n; compiling file \"\/home\/maarten\/quicklisp\/dists\/quicklisp\/software\/slime-v2.26\/contrib\/swank-presentations.lisp\" (written 15 OCT 2020 02:50:13 PM):\n.\n\n; \/home\/maarten\/.slime\/fasl\/2.26\/sbcl-1.4.6-1.fc28-linux-x86-64\/contrib\/swank-presentations.fasl written\n; compilation finished in 0:00:00.051\n; compiling file \"\/home\/maarten\/quicklisp\/dists\/quicklisp\/software\/slime-v2.26\/contrib\/swank-presentation-streams.lisp\" (written 15 OCT 2020 02:50:13 PM):\n.\n\n; \/home\/maarten\/.slime\/fasl\/2.26\/sbcl-1.4.6-1.fc28-linux-x86-64\/contrib\/swank-presentation-streams.fasl written\n; compilation finished in 0:00:00.048\n; compiling file \"\/home\/maarten\/quicklisp\/dists\/quicklisp\/software\/slime-v2.26\/contrib\/swank-asdf.lisp\" (written 15 OCT 2020 02:50:13 PM):\n....\n\n; \/home\/maarten\/.slime\/fasl\/2.26\/sbcl-1.4.6-1.fc28-linux-x86-64\/contrib\/swank-asdf.fasl written\n; compilation finished in 0:00:00.166\n; compiling file \"\/home\/maarten\/quicklisp\/dists\/quicklisp\/software\/slime-v2.26\/contrib\/swank-package-fu.lisp\" (written 15 OCT 2020 02:50:13 PM):\n.\n\n; \/home\/maarten\/.slime\/fasl\/2.26\/sbcl-1.4.6-1.fc28-linux-x86-64\/contrib\/swank-package-fu.fasl written\n; compilation finished in 0:00:00.011\n; compiling file \"\/home\/maarten\/quicklisp\/dists\/quicklisp\/software\/slime-v2.26\/contrib\/swank-hyperdoc.lisp\" (written 15 OCT 2020 02:50:13 PM):\n\n; \/home\/maarten\/.slime\/fasl\/2.26\/sbcl-1.4.6-1.fc28-linux-x86-64\/contrib\/swank-hyperdoc.fasl written\n; compilation finished in 0:00:00.003\n; compiling file \"\/home\/maarten\/quicklisp\/dists\/quicklisp\/software\/slime-v2.26\/contrib\/swank-sbcl-exts.lisp\" (written 15 OCT 2020 02:50:13 PM):\n\n; \/home\/maarten\/.slime\/fasl\/2.26\/sbcl-1.4.6-1.fc28-linux-x86-64\/contrib\/swank-sbcl-exts.fasl written\n; compilation finished in 0:00:00.022\n; compiling file \"\/home\/maarten\/quicklisp\/dists\/quicklisp\/software\/slime-v2.26\/contrib\/swank-mrepl.lisp\" (written 15 OCT 2020 02:50:13 PM):\n.........................................\n[package swank-api]..............................\n[package swank-mrepl].\n\n; \/home\/maarten\/.slime\/fasl\/2.26\/sbcl-1.4.6-1.fc28-linux-x86-64\/contrib\/swank-mrepl.fasl written\n; compilation finished in 0:00:00.044\n; compiling file \"\/home\/maarten\/quicklisp\/dists\/quicklisp\/software\/slime-v2.26\/contrib\/swank-trace-dialog.lisp\" (written 15 OCT 2020 02:50:13 PM):\n...........................\n[package swank-trace-dialog]..\n\n; \/home\/maarten\/.slime\/fasl\/2.26\/sbcl-1.4.6-1.fc28-linux-x86-64\/contrib\/swank-trace-dialog.fasl written\n; compilation finished in 0:00:00.056\n; compiling file \"\/home\/maarten\/quicklisp\/dists\/quicklisp\/software\/slime-v2.26\/contrib\/swank-macrostep.lisp\" (written 15 OCT 2020 02:50:13 PM):\n....................\n[package swank-macrostep].\n\n; \/home\/maarten\/.slime\/fasl\/2.26\/sbcl-1.4.6-1.fc28-linux-x86-64\/contrib\/swank-macrostep.fasl written\n; compilation finished in 0:00:00.051\n; compiling file \"\/home\/maarten\/quicklisp\/dists\/quicklisp\/software\/slime-v2.26\/contrib\/swank-quicklisp.lisp\" (written 15 OCT 2020 02:50:13 PM):\n\n; \/home\/maarten\/.slime\/fasl\/2.26\/sbcl-1.4.6-1.fc28-linux-x86-64\/contrib\/swank-quicklisp.fasl written\n; compilation finished in 0:00:00.004\n........................\n[package alexandria]..............................\n[package alexandria-2]...........................\n[package quicklisp-slime-helper]\nslime-helper.el installed in \"\/home\/maarten\/quicklisp\/slime-helper.el\"\n\nTo use, add this to your ~\/.emacs:\n\n  (load (expand-file-name \"~\/quicklisp\/slime-helper.el\"))\n  ;; Replace \"sbcl\" with the path to your implementation\n  (setq inferior-lisp-program \"sbcl\")\n\n\n(\"quicklisp-slime-helper\")\n*   \n\n\n<\/pre>\n<p>One variant of the Fermat test that cannot be fooled is called the Miller-Rabin test (Miller 1976; Rabin 1980). This starts from an alternate form of Fermat\u2019s Little Theorem, which states that if n is a prime number and a is any positive integer less than n, then a raised to the (n \u2212 1)-st power is congruent to 1 modulo n. To test the primality of a number n by the Miller-Rabin test, we pick a random number a and raise a to the (n \u2212 1)-st power modulo n using the expmod procedure. However, whenever we perform the squaring step in expmod, we check to see if we have discovered a &#8220;nontrivial square root of 1 modulo n,&#8221; that is, a number not equal to 1 or n\u22121 whose square is equal to 1 modulo n. It is possible to prove that if such a nontrivial square root of 1 exists, then n is not prime. It is also possible to prove that if n is an odd number that is not prime, then, for at least half the numbers a, computing a to n \u2212 1 this way will reveal a nontrivial square root of 1 modulo n. (This is why the Miller-Rabin test cannot be fooled.) Modify the expmod procedure to signal if it discovers a nontrivial square root of 1, and use this to implement the Miller-Rabin test with a procedure analogous to fermat-test. Check your procedure by testing various known primes and non-primes. Hint: One convenient way to make expmod signal is to have it return 0.<\/p>\n<p><img decoding=\"async\" class=\"aligncenter\" title=\"math\" src=\"http:\/\/bacon.umcs.lublin.pl\/~wolsk\/wp-content\/abstraction.png\" alt=\"math\"><br \/>\n&nbsp;<\/p>\n<p><a href=\"http:\/\/bacon.umcs.lublin.pl\/~wolsk\/wp-content\/debates.zip\">Presidential Candidates Debates:<\/a>&nbsp;&nbsp; &gt;&gt;&gt; Check the website:&nbsp;<a href=\"http:\/\/www.presidency.ucsb.edu\/debates.php\">http:\/\/www.presidency.ucsb.edu\/debates.php<\/a><br \/>\n<!--\n\n\n<h1> UPDATE (17 December 2020)<\/h1>\n\n\n\n\n<h2><strong>As promised, please find below the codes of our programs discussed recently: <\/strong><\/h2>\n\n\n<a href=\"http:\/\/bacon.umcs.lublin.pl\/~wolsk\/wp-content\/3December2020.lisp\">LISP codes 2020!<\/a>\n\n&nbsp;\n\n\n<h1> UPDATE (8 Fabruary 2021)<\/h1>\n\n\n\n\n<h2><strong>As promised, please find below another review our programs discussed recently: <\/strong><\/h2>\n\n\n<a href=\"http:\/\/bacon.umcs.lublin.pl\/~wolsk\/wp-content\/8January2021.lisp\">LISP codes 2021!<\/a>\n\n<a href=\"http:\/\/bacon.umcs.lublin.pl\/~wolsk\/wp-content\/HPS3.lisp\"><span style=\"display: inline-block; width: 0px; overflow: hidden; line-height: 0;\" data-mce-type=\"bookmark\" class=\"mce_SELRES_start\"><\/span>LISP codes (Hanoi)!<\/a>\n\n<a href=\"http:\/\/bacon.umcs.lublin.pl\/~wolsk\/wp-content\/doctor.lisp\">LISP codes (Doctor)!<\/a>\n\n<a href=\"http:\/\/bacon.umcs.lublin.pl\/~wolsk\/wp-content\/hello-doc.lisp\">Therapy Session (Doctor)!<\/a>\n\n<a href=\"http:\/\/bacon.umcs.lublin.pl\/~wolsk\/wp-content\/confession-example.txt\">Confession -- session example<\/a>\n\n<a href=\"http:\/\/bacon.umcs.lublin.pl\/~wolsk\/wp-content\/confession.lisp\">Confession -- Lisp code<\/a>\n\n<a href=\"http:\/\/bacon.umcs.lublin.pl\/~wolsk\/wp-content\/FranceFrance.lisp\">Map of France -- new Lisp code<\/a>\n\n<a href=\"http:\/\/bacon.umcs.lublin.pl\/~wolsk\/wp-content\/restart.lisp\">Home work! -- my two solutions<\/a>\n\n<a href=\"http:\/\/bacon.umcs.lublin.pl\/~wolsk\/wp-content\/debates.zip\">Presidential Candidates Debates:<\/a>&nbsp;&nbsp; &gt;&gt;&gt; Check the website:&nbsp;<a href=\"http:\/\/www.presidency.ucsb.edu\/debates.php\">http:\/\/www.presidency.ucsb.edu\/debates.php<\/a>\n--><\/p>\n","protected":false},"excerpt":{"rendered":"<p>http:\/\/mirror.us-midwest-1.nexcess.net\/gnu\/emacs\/windows\/emacs-27\/ http:\/\/www.sbcl.org\/platform-table.html https:\/\/www.quicklisp.org\/beta\/ To get started with the Quicklisp beta, download and load https:\/\/beta.quicklisp.org\/quicklisp.lisp C:\\Users\\maart&gt;cd c:\\home c:\\home&gt;sbcl &#8211;load quicklisp.lisp ==== quicklisp quickstart 2015-01-28 loaded ==== To continue with installation, evaluate: 0] (quicklisp-quickstart:install) ==== quicklisp installed ==== To load a system, use: (ql:quickload &#8220;system-name&#8221;) To find systems, use: (ql:system-apropos &#8220;term&#8221;) To load Quicklisp every time you &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/bacon.umcs.lublin.pl\/~wolsk\/?page_id=251\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Human Problem Solving&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":24,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"https:\/\/bacon.umcs.lublin.pl\/~wolsk\/index.php?rest_route=\/wp\/v2\/pages\/251"}],"collection":[{"href":"https:\/\/bacon.umcs.lublin.pl\/~wolsk\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/bacon.umcs.lublin.pl\/~wolsk\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/bacon.umcs.lublin.pl\/~wolsk\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/bacon.umcs.lublin.pl\/~wolsk\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=251"}],"version-history":[{"count":41,"href":"https:\/\/bacon.umcs.lublin.pl\/~wolsk\/index.php?rest_route=\/wp\/v2\/pages\/251\/revisions"}],"predecessor-version":[{"id":765,"href":"https:\/\/bacon.umcs.lublin.pl\/~wolsk\/index.php?rest_route=\/wp\/v2\/pages\/251\/revisions\/765"}],"up":[{"embeddable":true,"href":"https:\/\/bacon.umcs.lublin.pl\/~wolsk\/index.php?rest_route=\/wp\/v2\/pages\/24"}],"wp:attachment":[{"href":"https:\/\/bacon.umcs.lublin.pl\/~wolsk\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=251"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}