为什么这个 SBV 代码在达到我设置的限制之前就停止了?
Why does this SBV code stop before hitting the limit I set?
我有这个定理(不确定这个词是否正确),我想得到所有的解。
pairCube limit = do
m <- natural exists "m"
n <- natural exists "n"
a <- natural exists "a"
constrain $ m^3 .== n^2
constrain $ m .< limit
return $ m + n .== a^2
res <- allSat (pairCube 1000)
-- Run from ghci
extractModels res :: [[Integer]]
这是试图解决的问题:
存在无限对整数 (m, n),使得 m^3 = n^2 且 m + n 是一个完全平方数。最大的 m 小于 1000 的对是什么?
我知道实际答案,只是通过暴力破解,但我想使用 SBV。
然而,当我 运行 代码时,它只给出以下值(以 [m, n, a] 的形式):
[[9,27,6],[64,512,24],[]]
但是,还有其他几种 m 值小于 1000 的解未包括在内。
给个完整的程序总是好的:
{-# LANGUAGE ScopedTypeVariables #-}
import Data.SBV
pairCube :: SInteger -> Symbolic SBool
pairCube limit = do
(m :: SInteger) <- exists "m"
(n :: SInteger) <- exists "n"
(a :: SInteger) <- exists "a"
constrain $ m^(3::Integer) .== n^(2::Integer)
constrain $ m .< limit
return $ m + n .== a^(2::Integer)
main :: IO ()
main = print =<< allSat (pairCube 1000)
当我 运行 它时,我得到:
Main> main
Solution #1:
m = 0 :: Integer
n = 0 :: Integer
a = 0 :: Integer
Solution #2:
m = 9 :: Integer
n = 27 :: Integer
a = -6 :: Integer
Solution #3:
m = 1 :: Integer
n = -1 :: Integer
a = 0 :: Integer
Solution #4:
m = 9 :: Integer
n = 27 :: Integer
a = 6 :: Integer
Solution #5:
m = 64 :: Integer
n = 512 :: Integer
a = -24 :: Integer
Solution #6:
m = 64 :: Integer
n = 512 :: Integer
a = 24 :: Integer
Unknown
注意最后的Unknown.
本质上,SBV查询了Z3,得到了6个解;当 SBV 要求第 7 个时,Z3 说 "I don't know if there's any other solution." 对于非线性算法,这种行为是预期的。
为了回答原始问题(即找到最大值 m
),我将约束更改为:
constrain $ m .== limit
并将其与以下 "driver:"
相结合
main :: IO ()
main = loop 1000
where loop (-1) = putStrLn "Can't find the largest m!"
loop m = do putStrLn $ "Trying: " ++ show m
mbModel <- extractModel `fmap` sat (pairCube m)
case mbModel of
Nothing -> loop (m-1)
Just r -> print (r :: (Integer, Integer, Integer))
在我的机器上 运行 大约 50 分钟后,Z3 生成:
(576,13824,-120)
所以,很明显,基于 allSat
的方法导致 Z3 放弃的方式比我们修复 m
并自行迭代实际实现的更早。对于非线性问题,期望任何 faster/better 对通用 SMT 求解器的要求都太过分了..
我有这个定理(不确定这个词是否正确),我想得到所有的解。
pairCube limit = do
m <- natural exists "m"
n <- natural exists "n"
a <- natural exists "a"
constrain $ m^3 .== n^2
constrain $ m .< limit
return $ m + n .== a^2
res <- allSat (pairCube 1000)
-- Run from ghci
extractModels res :: [[Integer]]
这是试图解决的问题:
存在无限对整数 (m, n),使得 m^3 = n^2 且 m + n 是一个完全平方数。最大的 m 小于 1000 的对是什么?
我知道实际答案,只是通过暴力破解,但我想使用 SBV。
然而,当我 运行 代码时,它只给出以下值(以 [m, n, a] 的形式): [[9,27,6],[64,512,24],[]]
但是,还有其他几种 m 值小于 1000 的解未包括在内。
给个完整的程序总是好的:
{-# LANGUAGE ScopedTypeVariables #-}
import Data.SBV
pairCube :: SInteger -> Symbolic SBool
pairCube limit = do
(m :: SInteger) <- exists "m"
(n :: SInteger) <- exists "n"
(a :: SInteger) <- exists "a"
constrain $ m^(3::Integer) .== n^(2::Integer)
constrain $ m .< limit
return $ m + n .== a^(2::Integer)
main :: IO ()
main = print =<< allSat (pairCube 1000)
当我 运行 它时,我得到:
Main> main
Solution #1:
m = 0 :: Integer
n = 0 :: Integer
a = 0 :: Integer
Solution #2:
m = 9 :: Integer
n = 27 :: Integer
a = -6 :: Integer
Solution #3:
m = 1 :: Integer
n = -1 :: Integer
a = 0 :: Integer
Solution #4:
m = 9 :: Integer
n = 27 :: Integer
a = 6 :: Integer
Solution #5:
m = 64 :: Integer
n = 512 :: Integer
a = -24 :: Integer
Solution #6:
m = 64 :: Integer
n = 512 :: Integer
a = 24 :: Integer
Unknown
注意最后的Unknown.
本质上,SBV查询了Z3,得到了6个解;当 SBV 要求第 7 个时,Z3 说 "I don't know if there's any other solution." 对于非线性算法,这种行为是预期的。
为了回答原始问题(即找到最大值 m
),我将约束更改为:
constrain $ m .== limit
并将其与以下 "driver:"
相结合main :: IO ()
main = loop 1000
where loop (-1) = putStrLn "Can't find the largest m!"
loop m = do putStrLn $ "Trying: " ++ show m
mbModel <- extractModel `fmap` sat (pairCube m)
case mbModel of
Nothing -> loop (m-1)
Just r -> print (r :: (Integer, Integer, Integer))
在我的机器上 运行 大约 50 分钟后,Z3 生成:
(576,13824,-120)
所以,很明显,基于 allSat
的方法导致 Z3 放弃的方式比我们修复 m
并自行迭代实际实现的更早。对于非线性问题,期望任何 faster/better 对通用 SMT 求解器的要求都太过分了..